Add two integers using only bitwise operators?
In C#, is it possible to perform a sum of two 32-bit integers without using things like if..else, loops etc?
That is, can it be done using only the bitwise operations OR (|
), AND (&
), XOR (^
), NOT (!
), shift left (<<
) and shift right (>>
)?
Here is an example for your amusement
unsigned int myAdd(unsigned int a, unsigned int b)
{
unsigned int carry = a & b;
unsigned int result = a ^ b;
while(carry != 0)
{
unsigned int shiftedcarry = carry << 1;
carry = result & shiftedcarry;
result ^= shiftedcarry;
}
return result;
}
The loop could be unrolled. Number of times it executes, depends on the number of bits set in operands, but it's never greater than the width of unsigned int
. Once carry
becomes 0
, next iterations don't change anything.
Try this:
private int add(int a, int b) {
if(b == 0)
return a;
return add( a ^ b, (a & b) << 1);
}
Edit:
Corrected if
statement
Think about how addition happens bit by bit. Shift the values to get each bit of each operand in turn, then look at the four possible values for the two bits and work out what the result bit should be and whether there's a carry bit to worry about. Then see how the result and carry can be caculated using the bitwise ops.
static int binaryadd(int x, int y)
{
while (x != 0)
{
int c = y & x;
y = y ^ x;
x = c << 1;
}
return y;
}