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 machine is impersonal, it takes the pride away from a piece of work, the individual merits and defects that go along with all work that is not done by a machine—which is to say, its little bit of humanity.”
—Friedrich Nietzsche (1844–1900)
“Denotation by means of sounds and markings is a remarkable abstraction. Three letters designate God for me; several lines a million things. How easy becomes the manipulation of the universe here, how evident the concentration of the intellectual world! Language is the dynamics of the spiritual realm. One word of command moves armies; the word liberty entire nations.”
—Novalis [Friedrich Von Hardenberg] (1772–1801)