Bit Manipulation

A photo app has six on/off settings: grid lines, flash, timer, HDR, location tags and sound. You could store six separate true/false values. Or you could store one small number, where each binary digit is one switch: grid lines in the rightmost digit, flash in the next, then timer, and so on. Flash and timer on, everything else off, is 000110 in binary, which is the number 6. Saving, copying and comparing all six settings becomes one operation on that number.

File permissions, feature flags and chess engines all store state this way. You need a handful of operators that act on single bits, and a few tricks built from them.

#A number is a row of switches

In binary, each position is worth double the one to its right: 1, 2, 4, 8, 16, 32 and so on. A number is the sum of the positions that are on. So 44 is 32 + 8 + 4, written 101100. Positions are counted from the right, starting at 0: in 44, bits 2, 3 and 5 are on.

Six operators work on all the bits at once. Here they are applied to 12 (1100) and 10 (1010):

#The idea: masks

To touch one switch, build a mask: a number with only that bit on. 1 << i is exactly that, because it moves a single 1 into position i. Then combine the mask with your number:

• Check bit i: (x >> i) & 1 is 1 if it is on.
• Set it: x | (1 << i). OR with 1 forces a 1 and leaves the other bits alone.
• Clear it: x & ~(1 << i). The flipped mask has a 0 only at bit i, and AND with 0 forces a 0.
• Toggle it: x ^ (1 << i). XOR with 1 flips a bit.

const isOn = (x, i) => ((x >> i) & 1) === 1;
const turnOn = (x, i) => x | (1 << i);
const turnOff = (x, i) => x & ~(1 << i);
const flip = (x, i) => x ^ (1 << i);
 
let settings = 0;                // all six off
settings = turnOn(settings, 1);  // flash: 000010
settings = turnOn(settings, 2);  // timer: 000110, which is 6
isOn(settings, 2);               // true
settings = flip(settings, 1);    // flash off again: 000100, which is 4

def is_on(x, i):
    return ((x >> i) & 1) == 1
 
def turn_on(x, i):
    return x | (1 << i)
 
def turn_off(x, i):
    return x & ~(1 << i)
 
def flip(x, i):
    return x ^ (1 << i)
 
settings = 0                     # all six off
settings = turn_on(settings, 1)  # flash: 000010
settings = turn_on(settings, 2)  # timer: 000110, which is 6
is_on(settings, 2)               # True
settings = flip(settings, 1)     # flash off again: 000100, which is 4

#Drop the lowest 1 bit

One expression shows up again and again: x & (x - 1). It turns off the lowest bit that is on and keeps the rest. Subtracting 1 borrows from the lowest 1: that bit becomes 0 and every 0 below it becomes 1. AND with the original then wipes out exactly those positions. Repeat until nothing is left and you have counted the 1 bits.

count = 0while x != 0:  x = x & (x - 1)    # drop the lowest 1  count += 1

The same expression answers "is x a power of two?" A power of two has exactly one 1 bit, so dropping it leaves 0: x > 0 && (x & (x - 1)) === 0.

function countOnes(x) {
  let count = 0;
  while (x !== 0) {
    x &= x - 1; // drop the lowest 1
    count++;
  }
  return count;
}
 
const isPowerOfTwo = (x) => x > 0 && (x & (x - 1)) === 0;
 
countOnes(44);    // 3
isPowerOfTwo(32); // true
isPowerOfTwo(44); // false

def count_ones(x):
    count = 0
    while x != 0:
        x &= x - 1  # drop the lowest 1
        count += 1
    return count
 
def is_power_of_two(x):
    return x > 0 and (x & (x - 1)) == 0
 
count_ones(44)        # 3
is_power_of_two(32)   # True
is_power_of_two(44)   # False

In real Python code, x.bit_count() (Python 3.10 and later) does the counting for you. The trick still matters because the same "drop the lowest 1" step is used inside other algorithms, such as Fenwick trees.

#XOR finds the odd one out

A drawer holds socks with ID numbers. Every ID appears twice, except one sock that lost its partner: [4, 7, 2, 7, 4]. XOR has two properties that solve this with no extra memory. A number XOR itself is 0, and a number XOR 0 is itself. Order does not matter either. So XOR everything: each pair cancels, and only the lonely sock is left.

Step by step: 4 ^ 7 = 3, then 3 ^ 2 = 1, then 1 ^ 7 = 6, then 6 ^ 4 = 2. The middle values look random, but the pairs still cancel in the end.

function unpaired(ids) {
  let result = 0;
  for (const id of ids) result ^= id; // pairs cancel out
  return result;
}
 
unpaired([4, 7, 2, 7, 4]); // 2

def unpaired(ids):
    result = 0
    for sock_id in ids:
        result ^= sock_id  # pairs cancel out
    return result
 
unpaired([4, 7, 2, 7, 4])  # 2

#Subsets as numbers

Back to the sandwich extras from Backtracking: C, E and T. Any sandwich is a choice of on or off for each extra, which is exactly a 3-bit number. Mask 5 is 101: bits 0 and 2, so C and T. Counting from 0 to 2³ − 1 = 7 visits every sandwich once, with no recursion at all.

function subsetsByMask(items) {
  const result = [];
  for (let mask = 0; mask < (1 << items.length); mask++) {
    const subset = [];
    for (let i = 0; i < items.length; i++) {
      if ((mask >> i) & 1) subset.push(items[i]); // bit i on: take item i
    }
    result.push(subset);
  }
  return result;
}
 
subsetsByMask(["C", "E", "T"])[5]; // ["C", "T"]

def subsets_by_mask(items):
    result = []
    for mask in range(1 << len(items)):
        subset = [items[i] for i in range(len(items)) if (mask >> i) & 1]
        result.append(subset)
    return result
 
subsets_by_mask(["C", "E", "T"])[5]  # ['C', 'T']

#Common mistakes

#Check yourself

#What to practise next

Bit masks come back in harder dynamic programming problems, where a mask records which items are already used. The lowest-bit trick powers Fenwick trees.