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:
“Assumptions of male superiority are as widespread and deep rooted and every bit as crippling to the woman as the assumptions of white supremacy are to the Negro.... this is no more a man’s world than it is a white world.”
—Student Non-Violent Coordinating Committee, African American civil rights organization. SNCC Position Paper (Women in the Movement)
“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)