Bit Manipulation
A number is eight switches. A mask is a number with one switch on. AND, OR and XOR with a mask read, set, clear or flip exactly that switch and leave the rest alone.
Gray code: g(n) = n xor (n shr 1), so each bit of the code is the xor of two neighbouring bits of n. Counting up in ordinary binary can flip many bits at once, 7 to 8 flips four; in Gray code consecutive numbers always differ in exactly one bit. Row 0: 0 = 00000000 gives 00000000. Bit 7 is on the left in this table.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 5, with their answers.
From 1 - 1 to 1 the Gray code flips one bit. Which one?
Answer: Bit 0. The flipped bit is the lowest bit of n if n is odd, otherwise the bit just above n's lowest set bit.
From 2 - 1 to 2 the Gray code flips one bit. Which one?
Answer: Bit 1. The flipped bit is the lowest bit of n if n is odd, otherwise the bit just above n's lowest set bit.
From 3 - 1 to 3 the Gray code flips one bit. Which one?
Answer: Bit 0. The flipped bit is the lowest bit of n if n is odd, otherwise the bit just above n's lowest set bit.
From 4 - 1 to 4 the Gray code flips one bit. Which one?
Answer: Bit 2. The flipped bit is the lowest bit of n if n is odd, otherwise the bit just above n's lowest set bit.
From 5 - 1 to 5 the Gray code flips one bit. Which one?
Answer: Bit 0. The flipped bit is the lowest bit of n if n is odd, otherwise the bit just above n's lowest set bit.
How it runs, step by step
Gray code: g(n) = n xor (n shr 1), so each bit of the code is the xor of two neighbouring bits of n. Counting up in ordinary binary can flip many bits at once, 7 to 8 flips four; in Gray code consecutive numbers always differ in exactly one bit. Row 0: 0 = 00000000 gives 00000000. Bit 7 is on the left in this table.
Gray codes starting at 0.
n = 1 is 00000001; n shr 1 is 00000000; xor gives 00000001. Against the row above only bit 0 changed, while plain binary flipped 1 bit going from 0 to 1.
Gray code of 1 is 00000001, bit 0 flipped.
n = 2 is 00000010; n shr 1 is 00000001; xor gives 00000011. Against the row above only bit 1 changed, while plain binary flipped 2 bits going from 1 to 2.
Gray code of 2 is 00000011, bit 1 flipped.
n = 3 is 00000011; n shr 1 is 00000001; xor gives 00000010. Against the row above only bit 0 changed, while plain binary flipped 1 bit going from 2 to 3.
Gray code of 3 is 00000010, bit 0 flipped.
n = 4 is 00000100; n shr 1 is 00000010; xor gives 00000110. Against the row above only bit 2 changed, while plain binary flipped 3 bits going from 3 to 4.
Gray code of 4 is 00000110, bit 2 flipped.
n = 5 is 00000101; n shr 1 is 00000010; xor gives 00000111. Against the row above only bit 0 changed, while plain binary flipped 1 bit going from 4 to 5.
Gray code of 5 is 00000111, bit 0 flipped.
Six consecutive Gray codes, each one bit away from the last. That is why rotary encoders and Karnaugh maps use it: a single misread bit at a boundary is only ever off by one. Decoding is a running xor of the code's bits from the top down.
Gray code sequence complete.
Write it yourself
Define isPowerOfTwo(n) and return true when n is a power of two. It runs in your browser against this lesson's own 2 examples.
// A power of two has exactly one bit set, and subtracting one flips it and everything below it.function isPowerOfTwo(n) { return false;}
Remember
- 1 shl i is the mask for bit i. OR sets it, AND with the inverse clears it, XOR flips it.
- n and (n - 1) clears the lowest 1 bit. Loop it to count set bits in one round per 1.
- A power of two has exactly one 1 bit, so n and (n - 1) is zero for it and nothing else.
Topics covered
Related
Where this is used
Game enginesChess engine bitboards
Stockfish and most other strong engines store the board as a handful of 64-bit words, one per piece type, where bit i means a piece stands on square i. Move generation then becomes shifting and masking: all single white pawn pushes are the pawn word shifted by 8 and ANDed with the complement of the occupied word. n and -n pulls off one piece at a time so the engine iterates only the occupied squares instead of scanning all 64.
DatabasesRedis bitmaps
Redis addresses individual bits of a string with SETBIT and GETBIT, which is the usual way to track daily active users: one bit per user id per day, so ten million users cost about 1.2 MB a day. BITCOUNT is a population count over the whole string and BITOP AND intersects two days, so asking who was active on both days is a word-at-a-time AND rather than a join between two sets.
HardwareAbsolute rotary encoders
An absolute encoder reads several parallel tracks off a disc to report a shaft angle. In plain binary the step from 7 to 8 changes four tracks at once, and if the sensors are a hair out of line the reading passes through a garbage value on the way. Gray code is used instead precisely because consecutive positions differ in exactly one bit, so a misaligned read can only ever be off by one position.
Language runtimesPower-of-two hash tables
Java's HashMap keeps its table length a power of two so the bucket index is (length - 1) and hash instead of hash % length. The mask keeps the low bits in one instruction where an integer division costs tens of cycles. The same trick is behind ring buffers sized to a power of two, where wrapping the index around is an AND rather than a branch or a modulo.
Why it works this way
Why n and (n - 1) clears the lowest 1
Subtracting 1 flips the lowest 1 to a 0 and turns every 0 below it into a 1, while the bits above it are untouched. ANDing the two keeps only what they agree on, so that lowest 1 and the run of zeros beneath it all vanish together. Kernighan's loop therefore runs once per set bit rather than once per bit of width. The same identity carries the power-of-two test, and it is why that test needs the n > 0 guard: 0 and -1 is 0, and Int.MIN_VALUE and Int.MAX_VALUE is 0, so both would otherwise pass.
Why n and -n leaves exactly the lowest 1
In two's complement, -n means invert every bit and then add 1. That add carries through the trailing 1s of the inverted number, which were the trailing 0s of n, and stops at the lowest 1 bit - so -n matches n at and below that bit and is its opposite everywhere above. AND keeps only the part where they match, which is that single bit. It holds even at Int.MIN_VALUE, where negating overflows back to the same number.
Two traps when you shift
The shift count is taken modulo the width, so on an Int 1 shl 32 is 1 and not 0, and raising the count further wraps it back to the start rather than driving the value to zero. Bits do still fall off the top inside a single shift: 2 shl 31 is 0. And shr is arithmetic: it feeds the sign bit back in, so -8 shr 1 is -4, and a loop like while (x != 0) { x = x shr 1 } spins forever on a negative number. Use ushr when you want zeros shifted in. The n and (n - 1) loop sidesteps the question entirely, which is why it is the one used for counting here.
Gray code encodes in one line but decodes in a loop
n xor (n shr 1) is a local operation: output bit i depends only on input bits i and i + 1, so every bit is computed independently. Going back is not local, because a Gray bit only tells you whether the original value changed at that position - the original bit i is the XOR of every Gray bit from the top down to i. That is why fromGray keeps a running XOR of the shifted value instead of collapsing to a single expression.
Read more
- Bit manipulationWikipedia
- Bit Twiddling HacksStanford
- Bit manipulationcp-algorithms
- Two's complementWikipedia
- Gray codeWikipedia