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 :-
Check if a number is a power of 2 using bit operation.

Solution :-
Suppose the given number is 'x'. The trick is that if the AND operation of the x & x-1 is false,
then x is a power of 2.

#include<iostream>
using namespace std;

// check if a no. is power of two
bool isPowerOf2(int num) {
   if (num == 0) return false;
   // if a number 'num' is a power of 2 then
   // (num & num-1) is 0
   bool is_pow = !(num & (num-1));
   return is_pow;
}

// main
int main() {
   int num = 32;
   bool is_pow_2 = isPowerOf2(num);
   if (is_pow_2)
      cout<<"\n"<<num<<" is power of 2";
   else
      cout<<"\n"<<num<<" is not a power of 2";
   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