What is a ^ b and (a & b) << 1?
It's basically replicating the half-adder
Adding 2 bits A and B produces 2 outputs: a sum and a carry bit like below
╔═══════╤═════════════╗║ Input │ Output ║╠═══╤═══╪═══════╤═════╣║ A │ B │ carry │ sum ║╟───┼───┼───────┼─────╢║ 0 │ 0 │ 0 │ 0 ║╟───┼───┼───────┼─────╢║ 1 │ 0 │ 0 │ 1 ║╟───┼───┼───────┼─────╢║ 0 │ 1 │ 0 │ 1 ║╟───┼───┼───────┼─────╢║ 1 │ 1 │ 1 │ 0 ║╚═══╧═══╧═══════╧═════╝
From the table we get the logic for the outputs: carry = A and B, sum = A xor B
XOR is also called a carry-less add operator, and represented by ⊕ with the +
symbol inside
So the snippet above is working like this
const Sum=a^b; // sum = a xor b = a ⊕ bconst carry=(a&b)<<1; // carry = 2*(a and b), since we carry to the next bitif(!carry){ return Sum; // no carry, so sum + carry = sum}return getSum(Sum,carry); // a + b = sum + carry
So a^b
adds each bit in a and b simultaneously, leaving the non-carry sum of a and b in Sum
. Then we have to add carry to the carry-less sum to get the final result, since we have only a half-adder instead of a full-adder which does a + b = a ⊕ b + carry
See also
Let's learn by example. Imagine that a = 3
and b = 5
In binary notation they are a = 0011
and b = 0101
XOR:a^b
is XOR operator. When compare two bits it returns 0
if they are same and 1
if they are different. 01^10 => 11
So when we're doing a^b
result will be 0110
.
AND + SHIFT
a&b
performs logical AND operation. It returns 1 only when a = b = 1
.
In our case the result is 0001
<<
shifts it(adds 0
on the right side) and result became 0010
which sets carry
variable true. (only 0000
will be false).
Next iterations:
Everything repeats but now a = 0110
and b = 0010
(Sum
and carry
from last execution)
Now a^b = 0100
and (a&b)<<1 = 0100
Repeating again.
Now a^b = 0000
and (a&b)<<1 = 1000
And again.
Now a^b = 1000
and (a&b)<<1 = 0000
. Now carry
is finally false
. And we're returning 1000
which is decimal 8
.
Everything worked fine since 3+5=8
int result = p ^ q; // XOR Operator, + without carry 0+0=0, 0+1=1+0=1, 1+1=0int carry = (p & q) << 1; // Left Shift, 1+1=2if (carry != 0) { return getSum(result, carry);}return result;
Start By p=5,q=6. Then the XOR would be,
01010110------0011
So, XORing results in (0011) which is actually 3 in decimal. Then ANDing p and q we get,
01010110-------0100
We get 4 (100 in binary) by ANDing 5 & 6, now if we left shift this value by 1, we get
0100<<1=1000
So we get 8 (1000 in binary) after first recursion.As the result (carry variable) isnt zero, lets recursion again by xor value and carry value.
getSum(3, 8);
So, doing the first XORing we get,
00111000-------1011
The XORing this time yielded in 11 (1011 binary),so we perform the AND now,
00111000-------0000
We get all ZERO for ANDing 3 and 8, so this time the left shift operator also results in ZERO, as we have no 1 here which may give us a value by left shifing zeroes.As the carry variable is now Zero, we come to the end of recursion and the XORed value will be the Sum, which is 11 (1011 in Binary).
Hope you get the working of the procedure. You can learn more by learning bitwise operation, as its the way the machine do the arithmatic operations.