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:
“The public, with its mob yearning to be instructed, edified and pulled by the nose, demands certainties; it must be told definitely and a bit raucously that this is true and that is false. But there are no certainties.”
—H.L. (Henry Lewis)
“When we say “science” we can either mean any manipulation of the inventive and organizing power of the human intellect: or we can mean such an extremely different thing as the religion of science the vulgarized derivative from this pure activity manipulated by a sort of priestcraft into a great religious and political weapon.”
—Wyndham Lewis (1882–1957)