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...0If 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...0If 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).
Read more about this topic: Bit Manipulation
Famous quotes containing the words bit and/or manipulation:
“Take a decayed Christian ... and the remains of a Stoic; mix thoroughly with good manners, a bit of money and an old-fashioned education; simmer for several years in a university. Result: a scholar and a gentleman. Well, there were worse types of human being.”
—Aldous Huxley (1894–1963)
“The principle that human nature, in its psychological aspects, is nothing more than a product of history and given social relations removes all barriers to coercion and manipulation by the powerful.”
—Noam Chomsky (b. 1928)