Bit manipulation · about 45 min

Bit tricks

Why this matters

A handful of short bit expressions show up again and again in real code: in memory allocators (rounding sizes to alignment), hash tables (sizes that are powers of two so % size becomes a mask), graphics, compression, and the implementations of the standard library itself. They are not tricks for showing off. Each one follows from how binary subtraction and the bitwise operators work, and once you see why, you can derive them yourself instead of memorizing them.

All of the following assume unsigned types, where arithmetic wraps and no shift is undefined.

Subtracting one

The key observation: subtracting 1 from a binary number flips the lowest 1 bit to 0 and every 0 below it to 1, and leaves the higher bits alone.

  x       0101 1000   0x58
  x - 1   0101 0111   0x57
          ^^^^ unchanged, the lowest 1 and below are flipped

Combine that with &, | and ^ to isolate or remove the lowest set bit:

  x & (x - 1)    0101 0000   remove the lowest set bit
  x & -x         0000 1000   keep only the lowest set bit
  x ^ (x - 1)    0000 1111   mask up to and including the lowest set bit

-x on an unsigned value is ~x + 1, the two's complement negation from the types module, which flips all bits above the lowest 1. Verified in the sandbox:

uint32_t x = 0x58;
printf("%02X %02X %02X\n", x - 1, x & (x - 1), x & (~x + 1));   /* 57 50 08 */

Power of two test

A power of two has exactly one bit set. Removing the lowest set bit leaves zero exactly when there was only one:

int is_power_of_two(uint32_t x)
{
    return x != 0 && (x & (x - 1)) == 0;
}

The x != 0 matters: 0 & (0 - 1) is also 0.

Counting bits faster

The loop from the first lesson inspected all 32 positions. Clearing the lowest set bit repeatedly takes only as many steps as there are ones (Brian Kernighan's method):

int count = 0;
while (x != 0) {
    x &= x - 1;
    count++;
}

Powers of two make division cheap

For a power of two m, the low bits m - 1 form a mask:

  n % m   ==   n & (m - 1)          13 % 8 == 13 & 7 == 5
  n / m   ==   n >> log2(m)         13 / 8 == 13 >> 3 == 1
  round n down to a multiple of m:  n & ~(m - 1)
  round n up   to a multiple of m:  (n + m - 1) & ~(m - 1)     (13 -> 16)

The round-up formula: adding m - 1 pushes any n that is not already a multiple past the next multiple, then clearing the low bits rounds down to it. If n was already a multiple, adding m - 1 is not enough to reach the next one, so it stays. malloc implementations do exactly this to keep every block 16-byte aligned.

Hash tables often keep their size a power of two so that hash % size can be hash & (size - 1). (Modern compilers already turn % 8 on unsigned values into & 7, so write whichever is clearer; the mask form matters when size is a variable.)

Next power of two

Rounding up to the next power of two "smears" the highest set bit into every lower position, then adds one:

uint32_t v = 37;
v--;
v |= v >> 1;  v |= v >> 2;  v |= v >> 4;  v |= v >> 8;  v |= v >> 16;
v++;
printf("%u\n", v);    /* 64 */

Walk through it for 37: after v--, v is 36 = 0010 0100. The shifted ORs copy the top 1 into every lower position, giving 0011 1111 = 63, and adding 1 gives 0100 0000 = 64. The initial v-- is what keeps exact powers of two unchanged (64 stays 64 rather than becoming 128).

XOR's algebra

XOR has properties that make it unusually useful:

  a ^ 0 == a          a ^ a == 0          a ^ b == b ^ a          (a ^ b) ^ c == a ^ (b ^ c)

Consequences:

XOR is its own inverse. If c = a ^ key, then c ^ key == a. This is the heart of stream ciphers and of RAID 5 parity: lose any one disk and XOR the others to rebuild it.
Pairs cancel. XOR together a list in which every value appears twice except one, and the result is the unpaired value, in any order.
Toggling. x ^= mask flips the masked bits, as you saw with flags.

You may also see the "XOR swap":

a ^= b;  b ^= a;  a ^= b;    /* swaps a and b without a temporary */

It works, but do not use it: it is slower than a temporary on modern CPUs, harder to read, and if a and b are the same object (say, *p and *q with p == q) it sets it to zero.

Compiler builtins

CPUs have single instructions for counting bits, and gcc exposes them:

builtin	returns	for `0x58`
`__builtin_popcount(x)`	number of 1 bits	3
`__builtin_ctz(x)`	count trailing zeros (index of lowest 1)	3
`__builtin_clz(x)`	count leading zeros in a 32-bit `unsigned`	25

ctz and clz are undefined for 0. 31 - __builtin_clz(x) is the index of the highest set bit, that is floor(log2(x)). Variants ending in l and ll take unsigned long and unsigned long long. These are gcc and clang extensions, not standard C (C23 adds <stdbit.h> with standard names such as stdc_count_ones).

Common mistakes

Applying tricks to signed values. x & -x with x = INT_MIN overflows. Use unsigned.
Forgetting the zero case. x & (x - 1) says 0 is a power of two; __builtin_ctz(0) is UB.
Using & (m - 1) when m is not a power of two. n & 9 is not n % 10.
Missing parentheses. x & x - 1 == 0 parses as x & ((x - 1) == 0).
Being clever where clarity is free. The compiler already optimizes n % 8 and n / 8 for unsigned n. Use the tricks where they express something (alignment, flag manipulation) or the value is not a constant.

Recap

x - 1 flips the lowest set bit and the zeros below it; from that, x & (x - 1) clears the lowest set bit and x & -x isolates it.
Power of two: x && !(x & (x - 1)).
For power-of-two m: n & (m - 1) is n % m; (n + m - 1) & ~(m - 1) rounds up.
XOR cancels pairs and is its own inverse.
__builtin_popcount, __builtin_ctz and __builtin_clz map to single CPU instructions.

Going further: the classic collection is Sean Eron Anderson's "Bit Twiddling Hacks" (search for it), and the book Hacker's Delight by Henry Warren explains the reasoning behind hundreds of these. Try deriving x | (x + 1) (set the lowest zero bit) on paper before checking it.

Exercises

Exercise 1 · quiz

What does x & (x - 1) do?

For x = 0x58 (binary 0101 1000), what is x & (x - 1)?

Answer

0x50

x - 1 = 0101 0111: subtracting 1 turns the lowest 1 bit into 0 and every 0 below it into 1. ANDing with x keeps the bits above unchanged and clears the lowest 1 and everything below it: 0101 0000 = 0x50. So x & (x - 1) removes exactly the lowest set bit. Repeating it until x is 0 counts the set bits in as many steps as there are ones.

Exercise 2 · write code

Is it a power of two?

Write int is_power_of_two(uint32_t x) returning 1 if x is a power of two (1, 2, 4, 8, ...,

and 0 otherwise, without a loop: use the x & (x - 1) trick. Be careful with 0,

which is not a power of two.

main reads unsigned numbers until end of input and prints yes or no for each, one per line.

File: main.c

Starting point

#include <stdio.h>
#include <stdint.h>

int is_power_of_two(uint32_t x)
{
    return 0;
}

int main(void)
{
    unsigned x;
    while (scanf("%u", &x) == 1)
        printf("%s\n", is_power_of_two(x) ? "yes" : "no");
    return 0;
}

Example

input

0 1 2 3 64 96 1024 2147483648 4294967295

expected output

no
yes
yes
no
yes
no
yes
yes
no

Hint 1

A power of two has exactly one bit set. Clearing the lowest set bit leaves 0 only in that case.

Hint 2

0 & (0 - 1) is also 0, so test x != 0 as well.

Hint 3

Remember the parentheses: (x & (x - 1)) == 0.

Reference solution

#include <stdio.h>
#include <stdint.h>

int is_power_of_two(uint32_t x)
{
    return x != 0 && (x & (x - 1)) == 0;
}

int main(void)
{
    unsigned x;
    while (scanf("%u", &x) == 1)
        printf("%s\n", is_power_of_two(x) ? "yes" : "no");
    return 0;
}

Exercise 3 · write code

Round up to a multiple

Memory allocators and file formats constantly round sizes up to a multiple of a power of two (8, 16, 4096). Write

uint32_t align_up(uint32_t n, uint32_t align);

returning the smallest multiple of align that is greater than or equal to n. align is always a power of two. Use only +, -, & and ~ (no /, % or loops). You may assume the result fits in 32 bits.

main reads pairs n align until end of input and prints each result on its own line:

$ echo "13 8  16 8  0 4096  4097 4096" | ./prog
16
16
0
8192

File: main.c

Starting point

#include <stdio.h>
#include <stdint.h>

uint32_t align_up(uint32_t n, uint32_t align)
{
    return n;
}

int main(void)
{
    unsigned n, align;
    while (scanf("%u %u", &n, &align) == 2)
        printf("%u\n", (unsigned)align_up(n, align));
    return 0;
}

Example

input

13 8  16 8  0 4096  4097 4096

expected output

Example

input

7 1  7 2  8 2  1 16  31 32  33 32

expected output

Hint 1

For a power of two align, align - 1 is a mask of the low bits, and n & ~(align - 1) rounds n DOWN to a multiple.

Hint 2

To round up instead, add align - 1 first, then round down.

Hint 3

return (n + align - 1) & ~(align - 1);

Reference solution

#include <stdio.h>
#include <stdint.h>

uint32_t align_up(uint32_t n, uint32_t align)
{
    return (n + align - 1) & ~(align - 1);
}

int main(void)
{
    unsigned n, align;
    while (scanf("%u %u", &n, &align) == 2)
        printf("%u\n", (unsigned)align_up(n, align));
    return 0;
}

Exercise 4 · write code

The unpaired number

The input is a count n followed by n non-negative integers. Every value appears exactly twice, except one value that appears once. Print that value.

Do it in a single pass with one unsigned accumulator and no arrays, using XOR. (Why it works: a ^ a == 0, a ^ 0 == a, and XOR is commutative and associative, so pairs cancel out in any order.)

$ echo "7  4 1 2 1 2 9 4" | ./prog
9

File: main.c

Starting point

#include <stdio.h>

int main(void)
{
    int n;
    if (scanf("%d", &n) != 1)
        return 1;
    unsigned result = 0;
    for (int i = 0; i < n; i++) {
        unsigned x;
        if (scanf("%u", &x) != 1)
            return 1;
        /* combine x into result */
    }
    printf("%u\n", result);
    return 0;
}

Example

input

7  4 1 2 1 2 9 4

expected output

Example

input

1 42

expected output

Hint 1

One operator, applied to every value: result ^= x;

Reference solution

#include <stdio.h>

int main(void)
{
    int n;
    if (scanf("%d", &n) != 1)
        return 1;
    unsigned result = 0;
    for (int i = 0; i < n; i++) {
        unsigned x;
        if (scanf("%u", &x) != 1)
            return 1;
        result ^= x;
    }
    printf("%u\n", result);
    return 0;
}