AlgoScope

Bit Manipulation

algorithmintermediateTime O(1)Space O(1)

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.

0001021314051607

Isolate the lowest 1 bit of 88. 88 is 01011000 in binary. Bit 0 is on the left here, so each index is its bit number. The trick is n and (-n): negating flips every bit above the lowest 1 and leaves that one and the zeros below it alone.

How it runs, step by step

  1. Isolate the lowest 1 bit of 88. 88 is 01011000 in binary. Bit 0 is on the left here, so each index is its bit number. The trick is n and (-n): negating flips every bit above the lowest 1 and leaves that one and the zeros below it alone.

    Isolating the lowest set bit of 88.

  2. 88 and -88 = 8, which is bit 3 alone. This is the step a Fenwick tree takes to find its parent.

    The lowest set bit is 8, bit 3.

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;}
Ln 1, Col 16 linesTab indents; Escape then Tab leaves the editor. Ctrl-Enter runs, Cmd-Enter on a Mac.

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

Next up