The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

Bit Manipulation

Problem :-
Add two numbers without using any airthmetic operator.

Solution :-
We use the same logic which is used in digital adder.
Sum = bit1 XOR bit2. Carry = bit1 AND bit2.
See the recursive logic implementation below.

#include<iostream>
using namespace std;

// Add two no.s with using any airthmetic operator
int add(int a, int b) {
   if (b == 0) {
      // boundary case when there is no carry
      return a;
   }
   // find sum and carry and recursively call add
   // till carry is 0
   int sum = a ^ b;
   int carry = (a & b) << 1;
   return add(sum, carry);
}

int main() {
   int a = 15;
   int b = 17;
   int sum = add(a,b);
   cout<<"\nSum of "<<a<<" & "<<b<<" is "<<sum;
   cout<<endl;
   return 0;
}

Back | Next

All problems on Bit Manipulation
* Count the number of set bits in an integer
* Find out whether a bit in a particular position in the binary representation of an unsigned integer is set or not
* Check if a number is a power of 2 using bit operation.
* Add two numbers without using any arithmetic operator
* Find the number of bits which are to be flipped to convert one integer to another
* Reverse the bits of an unsigned integer