Implement Add,Subtract,Multiplication,Division Using Bit Manipulation

Addition
This One is Somewhat Logical and the Best also. This will work all kind of Inputs. The Logic Behind the Concept is described breifly here :
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.

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

Subtraction

 This is the C Program, to Subtract the Two Integers Without Using the Arithmetic Operator ‘-’.
This One is Somewhat Logical and the Best also. This will work all kind of Inputs. This is the Similar one as we seen on the How to Add two Numbers without using the Arithmetic Operator '+' - Method 3. 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.

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

Also, see here to implement add operator without using arithmetic operators at all.

Multiplication
This is the C Program, to Multiply the Two Integers Without Using the Arithmetic Operator ‘*’.

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.

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.

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

} 

Division

This is the C Program, to Divide the Two Integers Without Using the Arithmetic Operator ‘/’. 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.

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;

/* Division function Computes the quotient and remainder

of two numbers using bit shifting */ 
int division(int tempdividend, int tempdivisor) { 
 int quotient = 1;  
if (tempdivisor == tempdividend) {
 remainder = 0; return 1;
 } else if ( tempdividend < tempdivisor) {
      remainder = tempdividend; 
     return 0; 
   } 

/* Here divisor < dividend, therefore left shift (multiply by 2)

divisor and quotient */
while (tempdivisor <= tempdividend) {
  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);

}