Bit Manipulation - Example of Bit Manipulation

Example of Bit Manipulation

The following two code samples, written in the C++ programming language, both determine if the given unsigned integer x is a power of two.

// The obvious method unsigned int x = ...; bool isPowerOfTwo; if (x > 0) { while ((x % 2) == 0) { x = x / 2; } isPowerOfTwo = (x==1); } else isPowerOfTwo = false; // A method using bit manipulation bool isPowerOfTwo = x && !(x & (x - 1));

To understand the second method please note that powers of two have one and only one bit set in their binary representation:

x == 0...010...0 x-1 == 0...001...1 x & (x-1) == 0...000...0

If the number is not a power of two, it will have '1' in several places:

x == 0...1...010...0 x-1 == 0...1...001...1 x & (x-1) == 0...1...000...0

If inline assembler code is used, then an instruction that counts the number of 1's or 0's might be available (for example, the POPCNT instruction from the x86 instruction set).