Masks and the lowest 1 bit

A mask is a number whose 1 bits pick the places you want to work on. With a mask and one operator from lesson 2 you can test, set, clear or flip any bits you choose. This lesson also covers two short methods with the lowest 1 bit that appear in many algorithms.

One bit at a time

The mask for place k is 1 << k: a single 1 in place k. Each move uses the rule of its operator for the places where the mask has a 1, and leaves the other places alone:

x & (1 << k) != 0     # test: is place k a 1?
x >> k & 1            # the same test, as 0 or 1
x | (1 << k)          # set place k to 1
x & ~(1 << k)         # clear place k to 0
x ^ (1 << k)          # flip place k

To clear a place, the mask is turned around first: ~(1 << k) has a 1 in every place except k, so & keeps everything except place k. A mask with several 1s works on several places at once: x & 0xFF keeps the lowest 8 bits, and x | 0b1010 sets places 1 and 3.

Fields of several bits

Many formats pack several small values into one number, each in its own group of places, called a field. A colour such as 0x3366CC holds red, green and blue in 8 bits each. To read the field of width w that starts at place lo, shift it down to place 0 and keep w bits. To write it, clear the field, then | in the new value moved up to place lo:

def get_field(x, lo, w):
    return x >> lo & ((1 << w) - 1)

def set_field(x, lo, w, v):
    mask = ((1 << w) - 1) << lo
    return x & ~mask | (v << lo)

colour = 0x3366CC
get_field(colour, 16, 8)    # 0x33 = 51: red
get_field(colour, 8, 8)     # 0x66 = 102: green

Other examples are Unix file permissions (0o755 is three fields of 3 bits: read, write and run for the owner, the group and everyone else), the parts of a 32-bit network address, and the sign, power and fraction of a floating-point number. In Python, enum.Flag gives names to single-bit flags, so code can say Perm.READ | Perm.WRITE instead of 6.

The lowest 1 bit

Subtracting 1 from x borrows from the lowest 1 bit: that 1 becomes 0, every 0 below it becomes 1, and the places above it do not change. So x and x − 1 agree above the lowest 1 and never share a 1 from there down. That gives two short methods, shown in the second and third versions of the figure:

The second one works because −x = ~x + 1 (lesson 1). Flipping makes the 0s below the lowest 1 into 1s; adding 1 carries through them and stops at the lowest 1’s place. So −x has the same lowest 1 as x with 0s below it, and every bit above it is the opposite of x’s. Only that one place is 1 in both. The Fenwick tree of RNGQ-3 moves through its array with exactly this, i & -i.

• Is x a power of 2? A power of 2 has a single 1, so dropping it leaves 0: x > 0 and x & (x - 1) == 0.
• How many 0s at the bottom? (x & -x).bit_length() - 1, for x above 0. 88 is 1011000, so the answer is 3.
• The lowest 0 bit: x | (x + 1) sets it to 1, because adding 1 carries through the 1s at the bottom and stops at the lowest 0. ~x & (x + 1) keeps only that place.
• The highest 1 bit: 1 << (x.bit_length() - 1).

The next number with as many 1s

Lesson 5 will treat a number as a subset: bit i says whether item i is in it. Then the numbers with exactly k ones are the subsets of size k. Listing them smallest first needs a step from a number to the next larger number with the same count of 1s. Take 10011100, which has four 1s.

• Find the lowest run of 1s: the 1s from the lowest 1 bit upwards, until the first 0. Here it is 111 in places 2 to 4.
• Move the top 1 of the run up one place, into the 0 just above it (place 5).
• Move the other 1s of the run (two of them) down to the very bottom (places 0 and 1).

The result is 10100011. Why is it the next one? A larger number with the same count must turn some 0 into a 1, and to stay as small as possible that 0 must be as low as possible, with every place above it unchanged. The 1 it gains has to come from a place below it, so the 0 must have a 1 below it. The lowest such 0 is the one just above the lowest run. After that, the 1s that are left should be as low as possible: at the bottom.

Each part of this uses a method from this lesson: x & -x finds the lowest 1, and adding it to x carries through the run, clearing it and setting the 0 above. Putting the rest of the run at the bottom is BITS-P3. This step is often called Gosper’s hack, after Bill Gosper, who wrote it down in 1972.

Bit methods: when to use them

Bit methods common in C and in processors include swapping two numbers with three xors, the smaller of two numbers without an if, and multiplying by shifting. In Python these give no speed and make code harder to read: write a, b = b, a, min(a, b) and x * 2. Python spends its time on running each line, not on the arithmetic itself.

Now try BITS-P3, The next number with as many 1s.