Suppose we nedd to add two bits.We can simply use Half adder logic(kid’s stuff).In half adder sum of bits(S) is performed using bitwise XOR and carry of bits(C) is performed using bitwise AND.Now all we have to do is extend or further use the same logic for large number of bits.Bitwise XOR (^) of ‘a’ and ‘b’ gives the sum of ‘a’ and ‘b’ if ‘a’ and ‘b’ don’t have same bits at same positions.For example 2 ^ 3 will give you 1 while 2 ^ 5 will give 7 (See yourself).Now we can find carry using bitwise AND.All we need to calculate is (a & b) << 1 and then add it to a ^ b.This will be our desired answer.
Here’s the three step implementation of the above algorithm.:)
int add_numbers(int a, int b)
while (b != 0) // run loop untl carry is not zero
a = a ^ b; // Sum of bits of x and y
carry_out = a & b; // carry_out contains common bits of a and b
b = carry_out << 1; // Carry is shifted by one and then XOR is performed to get the desired answer