WAP to Implement Add,Subtract,Multiplication,Division Using Bit Manipulation

1st Approach to do the all operation

Addition

Here we use, One’s Complement Operator (~ - Known as Tilda). This is a Unary Operator. The output of “~b” means, One Complement of the value stored in ‘b’. For example, a=10, b=5. Then the ~b=-6. This operator simply works on the binary value of the corresponding Integer. As we know, One’s Complement is nothing but the Interchange of the 1’s and 0’s. So, If we give Input as b=5. The binary equivalent of 5 = 0000 0101 (Here we Consider that size of the Integer is 1 byte = 8 bits). Then the Complement of 5 = 1111 1010.Here the Most important thing is the Negative Numbers are stored in Computer as Two’s Complement Form. 2’s Complement = 1’s Complement + 1, And 1 111 1010, here the Left Most bit Represents the Sign of the Number, 1 indicates Negative, 0 Indicates Positive. So, Two’s Complement of 111 1010 is 000 0110 = 6, and of course, it is the Negative Number, so ~5 = -6. And Apply in the Expression, a-~b-1 = 10–(-6)-1 = 10+6–1 = 15. Simple Expression, But with Logic.

#include
#include

void main()
{
int a,b,sum;
clrscr();

printf("Enter 2 No.s : ");
scanf("%d%d",&a,&b); // Read 2 Integers

sum = a - ~b - 1; /* For the Explanation, See the Comments on Top */

printf("\nSum : %d",sum);
getch();
}

Subtraction
The Only difference here is the interchage of operators. Thats All.

For example, Assume that a=10, b=5. We know the difference is 5. Here we use the ‘~’ Operator in b. So ~b = – 6. Then a + ~b + 1 = 10 +(-6)+1 = 5. Simple Expression, But with Logic.

#include
#include

void main()
{
int a,b,sub;
clrscr();

printf("Enter 2 No.s : ");
scanf("%d%d",&a,&b); // Read 2 Integers

sub = a + ~b + 1; /* For the Explanation, See the Comments on Top */

printf("\nSubtraction : %d",sub);
getch();
}

Multiplication

This One is the Simply Logical. This will work all kind of Inputs. The concept behind this is We need to add the First Number, for Second Number Times. That’s All.

For example, Assume that a=5, b=4. We know the Answer is 20. Here we need to do is Adding the Number 5 itself,for 4 times. So We get the Answer as 20.

For better performance always add the Big Number,for Small Number Times. For Example to Multiply 5 * 100, better we Add 100,for 5 times, rather than adding 5, for 100 times.

#include
#include

void main()
{
int i,a,b,mul,big,small;
clrscr();

printf("Enter 2 No.s :\n");
scanf("%d%d",&a,&b); // Read 2 Numbers

if(a>b) // To find which is the Big one to Add Small one Times
{
big=a;
small=b;
}

else
{
big=b;
small=a;
}

mul=0; // Initialize the Variable to zero for Storing the Answer.

 for(i=1;i<=small;i++) // Adding Big Number, for Small Number Times. 
 {
     mul+=big; 
     printf("\n%d Times %d = %d",i,big,mul); 
 }
     printf("\n\nThe Answer is %d",mul); getch();
} 

 Division

This One is the Simply Logical. This will work all kind of Inputs. The concept behind this is We need to Perform the Reverse Operation performed on the Mutiplication Without '*' Opreator. Here we need to Subtract the Second Number From the First Number Until First Number >= Second Number. That’s All.

For example, Assume that a=10, b=3. Here we need to do is Subtract the Number 3 from the number 10 itself, until a>=b. And we should make a count for how many times we are doing like this, It is the Quotient Value.

So, finally We get the Answer as 3 Times we subtract 3 from the Number 10. Because we are checking the Condition a>=b everytime. So the is the Quotient as 3. The Remainder will be stored itself in 'a' as 1.

#include
#include

void main()
{
int a,b,c;
clrscr();

printf("Enter 2 No.s :\n");
scanf("%d%d",&a,&b); // Read 2 Numbers

if(b==0) // Here we are Checking for the Divide By Zero Error
{
printf("\nDivide By Zero Error");
}

else
{
c=0; // Here c as Count, and we should initialize the Count value to 0.
while(a>=b) // We Repeatedly Checking for the Condition a>=b
{
a = a - b; // Subtract b from a, and the new result stored in 'a' itself
c++; // Incrementing the Count
}

printf("\nQuotient = %d \n Remainder = %d",c,a); // Print Quotient and Remainder
}

getch();
}


Pure Low level Implementation (Bit Manipulation)

Lets Try For Decimal Integer Number how we add them

1 Add 759 + 674, but “forget” to carry I then get 323
2 Add 759 + 674 but only do the carrying, rather than the addition of each digit I then
get 1110
3 Add the result of the first two operations (recursively, using the same process de-
scribed in step 1 and 2): 1110 + 323 = 1433

we have done for decimal numbers

Now, how would we do this in binary?

1 If I add two binary numbers together but forget to carry, bit[i] will be 0 if bit[i] in a and
b are both 0 or both 1 This is an XOR
2 If I add two numbers together but only carry, I will have a 1 in bit[i] if bit[i-1] in a and b
are both 1’s This is an AND, shifted

3 Now, recurse until there’s nothing to carry

int add_no_arithm(int a, int b)
{
if (b == 0) return a;
int sum = a ^ b; // add without carrying
int carry = (a & b) << 1; // carry, but don’t add return add_no_arithm(sum, carry); // recurse 
 }

 Subtraction int sub(int x, int y)
{
      return(add(x,add(~y,1));

}

 Multiplication m=0;
 while (a)
 {
     if (a&1)
      m+=b; a>>=1;
     b<<=1; 
 }
printf("%d\n",m); The above code is a implementation of an algorithm better known as the Ethiopian 

Multiplication or the Russian Peasant Multiplication. Here’s the algorithm : 
 1. Let the two numbers to be multiplied be a and b. 
 2. If a is zero then break and print the result. 
 3. If a is odd then add b to the result. 
 4. Half a, Double b. Goto Step 2.

 Algorithm For Division :
 Given a dividend and a divisor would be to left shift (multiply by 2) the divisor till it reaches dividend/2, then continue this routine with the the difference between the dividend and divisor and divisor till the point where dividend is less than divisor or their difference is zero. This is similar to finding an element in a sorted list using the binary search algorithm, the C code is furnished below. #include

int dividend=17, divisor=2 , remainder;

int division(int tempdividend, int tempdivisor) 
{
int quotient = 1;

if (tempdivisor == tempdividend) {
remainder = 0;
return 1;
} else if (tempdividend < tempdivisor) { remainder = tempdividend; return 0; } while (tempdivisor <= tempdividend) { /* Here divisor < dividend, therefore left shift (multiply by 2) divisor and quotient */ tempdivisor = tempdivisor << 1; quotient = quotient << 1; } /* We have reached the point where divisor > dividend,
therefore divide divisor and quotient by two */
tempdivisor = tempdivisor >> 1;
quotient = quotient >> 1;

printf("\n %d %d", dividend, divisor);

/* Call division recursively for the difference to get the
exact quotient */
quotient = quotient + division(tempdividend - tempdivisor, divisor);

return quotient;
}

/* Division of two numbers without using division operator */
int main()
{
printf("\n%d / %d: quotient = %d", dividend, divisor, division(dividend, divisor));
printf("\n%d / %d: remainder = %d", dividend, divisor, remainder);

}

Run Here https://ideone.com/aSbGn

Source
http://www.prasannatech.net/2009/01/division-without-division-operator_24.html
http://courses.cs.vt.edu/~cs1104/BuildingBlocks/divide.030.html