Bit tricks

The command ls -l prints a file's permissions as a string like rwxr-xr--, and chmod takes them as the number 754. They are the same thing: nine flags, “may the owner, the group or the others read, write, execute”, written as nine bits of a number. 7 is 111, all three permissions, 5 is 101, read and execute, 4 is 100, read only. Below is a sixteen-bit number whose bits can be flipped one at a time, and tricks that do something useful with it in one operation.

Choose x & (x − 1) and look at the column: subtracting one turns the lowest one of the number into a zero and the zeros below it into ones; “and” with the original number wipes all of this out together with that one. The other bits do not change. Press “Make the result x” a few times: the ones disappear one by one from right to left, and the counter reaches zero in as many steps as there are ones in the number.

The idea

A number of n bits is a subset of a set of n elements: bit i is one if element i is in the subset. Then operations on sets are operations on bits: union is “or” (a | b), intersection is “and” (a & b), difference is “and” with a negation (a & ~b), membership is a bit test (a >> i & 1). The processor does each of them on 64 bits in one instruction, without loops or branches.

How numbers are stored in binary, what two's complement is and why −1 is all ones is told in the course chapter on bits. Here are the tricks that follow from it.

Tricks

• x & (x − 1) clears the lowest one. Hence counting the ones in as many steps as there are: clear until zero. Peter Wegner described the trick in 1960, and it became widely known through an exercise in Kernighan and Ritchie's book on C. And the test “is it a power of two”: a power of two has a single one, and clearing it leaves zero.
• x & −x keeps only the lowest one. In two's complement −x = ~x + 1: all bits flip, and the added one runs through the flipped bits up to the lowest one of x. Only that bit coincides with x. The Fenwick tree rests on this step: from position i it jumps by i & −i.
• x | (x + 1) sets the lowest zero, the mirror trick.
• Counting ones in one instruction. Processors have an instruction for this (POPCNT on x86); in Go bits.OnesCount reaches it, in Python int.bit_count() since version 3.10. The problem on a back-and-forth counter rests on it: the number of bits that flip between a and b is the number of ones in a XOR b.
• Shifts multiply and divide by powers of two, and interleaving the bits of two coordinates gives the Z-order from the article on space-filling curves.
• The Gray code x ^ (x >> 1) numbers the integers so that neighbours differ in one bit. Frank Gray of Bell Labs patented it for transmitting signals as pulses, and today it numbers the positions of angle sensors: at the boundary between two positions the sensor will not report a random third.

Masks turn up far beyond programming contests. Unix permissions are nine bits, and chmod g+w is an “or” with the mask 0o020. A /24 subnet mask is 24 ones, 255.255.255.0, and the network address is the address & the mask. Chess programs keep the position as “bitboards”: a 64-bit number for each kind of piece, and all knight moves from all squares at once are computed with shifts and masks. A large collection of such tricks is Henry Warren's book “Hacker's Delight”.

Going through subsets

Since a subset is a number, going through all subsets of a set of n elements means going through the numbers from 0 to 2ⁿ − 1. No recursion and no lists. Take the 16 items from the article on the knapsack and go through all 65,536 sets. The weight of a set need not be added up anew: a set is the same set without its lowest item plus that item, and weight[mask] = weight[mask ^ lowest] + weight of the item is one addition per set.

Two related tricks. To go through only the sets of exactly k items, Gosper's hack helps: a formula that turns a number with k ones into the next larger number with the same number of ones; Bill Gosper wrote it down in the HAKMEM collection in 1972. And the loop s = (s − 1) & m goes through all subsets of a given mask m: subtracting one and then “and” gives the next submask in decreasing order.

This matters for dynamic programming over masks: going through the submasks of all masks for 20 elements takes 3.5 billion steps, not 2⁴⁰, a trillion.

Code

Permissions, counting ones and the lowest bit, an exhaustive search over hiking sets, Gosper's hack and a check of the 3ⁿ formula:

The exhaustive search finds the same 64 points as the dynamic programming table in the article on the knapsack, and confirms its answer without trusting the recursion. 65,536 sets are a trifle; 40 items would already give a trillion, and then you need a table or meet in the middle, which goes through two halves of 2²⁰.

What it costs

An operation on a word is one processor instruction, so sets of 64 elements are united, intersected and tested in O(1). For larger sets there are bit arrays: n bits in n/64 words, and operations on a whole set cost O(n/64), 64 times cheaper than element by element. Going through subsets is 2ⁿ, through the submasks of all masks 3ⁿ, and in practice the limits are about 25 and 16 elements respectively.

The price is readability. Nobody will recognise x & -x in code without a comment, except those who already know it. So bit tricks are hidden in functions with clear names, like bits.OnesCount and int.bit_count, with a note of what they do.

Problems

The problem is chmod: permissions are changed by octal numbers and symbolic commands like go-w or u=rwx,g=rx,o=, and each command is one or two bit operations with masks.