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:
“So far we have been going firmly ahead, feeling the firm ground of prejudice glide away beneath our feet which is always rather exhilarating, but what next? You will be waiting for the bit where we bog down, the bit where we take it all back, and sure enough that’s going to come but it will take time.”
—J.L. (John Langshaw)
“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)