Bit manipulation

Introduction

Inside the computer, an int is a row of bits. Working on those bits directly is fast (one instruction) and compact (32 yes/no flags in one number). Operating systems pack permissions into bits, graphics code packs colours, chess engines store a whole board in 64 bits, and many interview problems have a one-line bit solution.

Bit operations look cryptic at first, but only a handful of patterns are in everyday use. Once you know them, a single int becomes a compact set of up to 32 flags.

How it works

The operators

There is also |, OR: 1 where either is 1, so 12 | 10 = 1110 = 14. Bits are numbered from 0 on the right, and 1 << k is a number with only bit k set: a mask.

Single bits

(x >> k) & 1      // is bit k set?          (1 or 0)
x | (1 << k)      // set bit k
x & ~(1 << k)     // clear bit k
x ^ (1 << k)      // flip bit k
x & (x - 1)       // clear the lowest set bit
x & -x            // keep only the lowest set bit

x - 1 flips the lowest 1 and every 0 below it, which is why x & (x - 1) removes exactly that bit. A power of two has a single 1 bit, so x is a power of two when x > 0 and x & (x - 1) is 0.

#include <stdio.h>

void show(unsigned x) {                   // the 8 lowest bits, highest first
    for (int k = 7; k >= 0; k--) printf("%u", (x >> k) & 1);
    printf("  (%u)\n", x);
}

int main(void) {
    unsigned x = 44;                      // 00101100
    show(x);
    show(x | (1u << 0));                  // set bit 0
    show(x & ~(1u << 2));                 // clear bit 2
    show(x ^ (1u << 7));                  // flip bit 7
    show(x & (x - 1));                    // clear the lowest set bit
    show(x & -x);                         // keep only the lowest set bit
    printf("44 is a power of two: %d\n", (x & (x - 1)) == 0);
    printf("32 is a power of two: %d\n", (32 & 31) == 0);
    return 0;
}

Counting the 1 bits by clearing the lowest one each time loops once per 1 bit, not once per bit. (GCC also has __builtin_popcount, which uses a single machine instruction.)

XOR tricks

• x ^ x = 0 and x ^ 0 = x, and the order does not matter. XOR a list where every number appears twice except one, and the pairs cancel: what is left is the single number. O(n) time, O(1) memory.
• a ^= b; b ^= a; a ^= b; swaps two variables without a third. It is a famous trick, but a temporary variable is clearer and just as fast: do not use it in real code.

Syntax

for (int mask = 0; mask < (1 << n); mask++)   // every subset
    for (int i = 0; i < n; i++)
        if (mask & (1 << i)) use(i);          // item i is in this subset

Example

A set of n items has 2ⁿ subsets. Number them 0 to 2ⁿ − 1: in mask number s, bit i says whether item i is in the subset. One loop lists them all, with no recursion:

#include <stdio.h>

int main(void) {
    const char *items[] = {"pen", "book", "cup"};
    int n = 3;
    for (int mask = 0; mask < (1 << n); mask++) {   // 000 up to 111
        printf("{");
        for (int i = 0; i < n; i++)
            if (mask & (1 << i)) printf(" %s", items[i]);
        printf(" }\n");
    }
    return 0;
}

This is the basis of bitmask dynamic programming, for example the travelling salesman problem on up to about 20 cities, where dp[mask][city] is the shortest route through the cities in mask.

Line by line

1. items holds the three names, and n is how many there are.
2. 1 << n is 8, so mask runs from 0 to 7, which is 000 to 111 in binary.
3. Each value of mask stands for one subset, so the outer loop runs 8 times.
4. The inner loop tests each bit, and mask & (1 << i) is non-zero when item i is included.
5. Each line of output shows one subset, starting with the empty one.

Expected result

{ }
{ pen }
{ book }
{ pen book }
{ cup }
{ pen cup }
{ book cup }
{ pen book cup }

In the real world

File permissions on Linux are three groups of three bits, which is why people write chmod 755. Network addresses, compressed file formats and graphics code all pack data into bits, and chess programs store a board position in a few 64-bit numbers.

Common mistakes

• Precedence: x & 1 == 0 means x & (1 == 0), which is always 0. Write (x & 1) == 0.
• Shifting by the number's width or more (1 << 32 for a 32-bit int) is undefined in C. Use 1ULL << k for bits up to 63.
• Right-shifting negative numbers: whether new bits are 0 or 1 depends on the compiler. Use unsigned for bit work.

Best practices

• Use unsigned types for bit work.
• Give every mask a name, or a comment that says what it means.
• Use parentheses in every expression that mixes bit operators with comparisons.

Summary

Bit operators work on the binary digits of a number directly. A few patterns test, set, clear and flip bits, a mask from 0 to 2ⁿ − 1 lists every subset, and XOR cancels pairs.

Mark lesson complete