Bit manipulation tricks

Test bit n

(x & (1u << n)) != 0

In this C, x is a uint8_t.

Is bit n of x a 1?

1u << n is a mask with a single 1 at position n. AND keeps a bit only where both inputs are 1, so every other position becomes 0 and the result is non-zero exactly when x has a 1 at position n.

(x >> n) & 1 gives the same answer as 0 or 1 instead of zero or non-zero.

Example at 8 bits: x = 0101 1000 (88), bit n = 3 gives true. Trace it bit by bit

Set bit n

x | (1u << n)

In this C, x is a uint8_t.

Turn bit n on and leave the others alone.

OR with 0 leaves a bit as it was and OR with 1 makes it 1. The mask is 0 everywhere except position n, so only that bit can change.

Example at 8 bits: x = 0101 1000 (88), bit n = 2 gives 0101 1100 (92). Trace it bit by bit

Clear bit n

x & ~(1u << n)

In this C, x is a uint8_t.

Turn bit n off and leave the others alone.

~ inverts the single-bit mask, giving all ones with a 0 at position n. AND with 1 leaves a bit as it was and AND with 0 clears it, so only bit n can change.

Example at 8 bits: x = 0101 1000 (88), bit n = 4 gives 0100 1000 (72). Trace it bit by bit

Toggle bit n

x ^ (1u << n)

In this C, x is a uint8_t.

Flip bit n: a 0 becomes 1 and a 1 becomes 0.

XOR with 1 inverts a bit and XOR with 0 leaves it alone. Applying the same toggle twice gets x back, which is what makes XOR useful for flags and for the swap trick further down.

Example at 8 bits: x = 0101 1000 (88), bit n = 6 gives 0001 1000 (24). Trace it bit by bit

Clear the lowest set bit

x & (x - 1)

In this C, x is a uint8_t.

Turn off the rightmost 1 and keep everything above it.

Subtracting 1 borrows from the lowest 1: that bit becomes 0 and every 0 below it becomes 1, while the bits above it do not change. So x and x − 1 agree above the lowest 1 and are opposite at and below it.

AND keeps the agreeing bits and zeroes the rest, which removes exactly the lowest 1. For x = 0 the result is 0.

Example at 8 bits: x = 0101 1000 (88) gives 0101 0000 (80). Trace it bit by bit

Isolate the lowest set bit

x & -x

In this C, x is a uint8_t.

Keep only the rightmost 1.

In two's complement −x is ~x + 1. Inverting x turns its trailing 0s into 1s and its lowest 1 into a 0; adding 1 carries through those 1s and stops at that 0, setting it. So −x matches x at the lowest 1 and below it, and is the inverse of x above it.

AND therefore leaves only the lowest 1. It works on an unsigned type too: the negation wraps round the same way. For x = 0 the result is 0.

Example at 8 bits: x = 0101 1000 (88) gives 0000 1000 (8). Trace it bit by bit

Is x a power of two?

x != 0 && (x & (x - 1)) == 0

In this C, x is a uint8_t.

True for 1, 2, 4, 8 and so on, false for anything else.

A power of two has exactly one bit set. Clearing the lowest set bit with x & (x − 1) leaves 0 only if there was no other set bit.

0 also gives 0 from x & (x − 1), which is why the x != 0 test is needed.

Example at 8 bits: x = 0100 0000 (64) gives true. Trace it bit by bit

Count trailing zeros

__builtin_popcount((uint8_t)((x & -x) - 1))

In this C, x is a uint8_t.

How many 0s sit below the lowest 1, which is also the index of the lowest set bit.

x & −x isolates the lowest set bit. Subtracting 1 turns that single 1 into 0 and every 0 below it into a 1, so the result has exactly as many 1s as x has trailing zeros. Counting them gives the answer.

For x = 0 this gives the width, because 0 − 1 is all ones at the width. At 8 and 16 bits C needs the cast back to the width for that: x & −x is worked out in int, so without the cast 0 − 1 is a 32-bit −1 and the count comes out as 32. GCC and Clang have __builtin_ctz, which compiles to a hardware instruction where the processor has one, but its result for 0 is undefined; C23 adds stdc_trailing_zeros, which returns the width for 0.

Example at 8 bits: x = 0101 1000 (88) gives 3. Trace it bit by bit

Count set bits (Kernighan's loop)

for (c = 0; x; c++) x &= x - 1;

In this C, x is a uint8_t.

Count the 1 bits by clearing them one at a time.

Each pass of x &= x − 1 clears the lowest set bit, so the loop runs once per 1 in x and stops when none are left. A number with three set bits takes three passes, whatever its width.

It is often credited to Brian Kernighan because The C Programming Language uses it in an exercise; Peter Wegner published it in 1960. It is fastest when few bits are set; the SWAR version below takes the same number of steps for every value.

Example at 8 bits: x = 0101 1000 (88) gives 3. Trace it bit by bit

Count set bits (SWAR)

x = x - ((x >> 1) & 0x55);
x = (x & 0x33) + ((x >> 2) & 0x33);
x = (x + (x >> 4)) & 0x0F;
/* x is now the count */

In this C, x is a uint8_t.

Count the 1 bits in a fixed number of steps, adding neighbouring fields in parallel.

SWAR means SIMD within a register: the number is treated as many small fields, and one subtraction or addition works on all of them at once. After the first line each 2-bit field holds the number of 1s that were in it (a pair ab is worth 2a + b, and subtracting a leaves a + b). The second line adds neighbouring pairs into 4-bit counts, the third adds nibbles into byte counts.

At 16 and 32 bits one more line adds the bytes together: the multiply by 0x0101 (0x01010101 at 32 bits) adds every byte into the top byte, and the shift brings that sum down. Nothing carries between fields because no count can outgrow its field: a 4-bit field holds at most 4, a byte at most 8.

At 16 bits the product has to be cut back to 16 bits before the shift. C multiplies a uint16_t as an int, so without the (uint16_t) cast the byte that lands above bit 15 survives and the shift brings it down as well: 0xFFFF would count as 2064 instead of 16.

Example at 8 bits: x = 0101 1000 (88) gives 3. Trace it bit by bit

Parity

x ^= x >> 4;
x ^= x >> 2;
x ^= x >> 1;
parity = x & 1;

In this C, x is a uint8_t.

Is the number of 1 bits odd? 1 for odd, 0 for even.

XOR of two bits is 1 when exactly one of them is 1, so the XOR of a set of bits is the parity of that set. Folding the top half onto the bottom half with x ^= x >> (width / 2) keeps the parity of the whole in the bottom half; halving again and again leaves it in bit 0.

Parity is the idea behind a parity bit on a serial line or a memory word: one extra bit chosen so the total number of 1s is even, which catches any single flipped bit.

Example at 8 bits: x = 0101 1000 (88) gives 1. Trace it bit by bit

XOR swap

x ^= y;
y ^= x;
x ^= y;

In this C, x and y are uint8_t values.

Swap two variables without a temporary.

XOR is its own inverse: (a ^ b) ^ b = a. After the first line x holds x ^ y. The second line computes y ^ (x ^ y), which is the original x. The third computes (x ^ y) ^ x, which is the original y.

It is a curiosity rather than an optimisation: compilers swap through a register, which is as fast or faster, and the three XORs depend on each other so they cannot run in parallel. It also fails when both names refer to the same variable: the first XOR sets it to 0 and the value is lost.

Example at 8 bits: x = 0101 1000 (88), y = 54 gives x = 54, y = 88. Trace it bit by bit

Do x and y have opposite signs?

(x ^ y) < 0

In this C, x and y are int8_t values.

True when one is negative and the other is not.

In two's complement the top bit is the sign: 1 for negative, 0 for zero or positive. XOR of the two top bits is 1 exactly when they differ, and a 1 in the top bit makes the result negative. So one XOR and one sign test replace (x < 0) != (y < 0).

Zero counts as non-negative here, so 0 and 5 do not have opposite signs, and 0 and −5 do.

Example at 8 bits: x = 0101 1000 (88), y = −42 gives true. Trace it bit by bit

Absolute value without a branch

int8_t m = x >> 7;
(x + m) ^ m

In this C, x is an int8_t.

|x| using a shift, an add and an XOR, with no if.

Shifting a signed value right by width − 1 copies the sign bit into every position: m is all ones (−1) for a negative x and 0 otherwise. For x ≥ 0, (x + 0) ^ 0 is x. For x < 0, x + m is x − 1, and XOR with all ones inverts it, and ~(x − 1) = −x.

It relies on the right shift being arithmetic, which C leaves to the implementation for negative values (GCC and Clang do shift arithmetically). The most negative value has no positive partner. At 8 bits C works out (x + m) ^ m in int, where −128 gives 128; stored back in an int8_t that is the pattern 1000 0000, which reads as −128 again. At 32 bits it is worse: for INT_MIN the x + m itself overflows, which is undefined behaviour, just as abs(INT_MIN) is.

Example at 8 bits: x = 1101 0110 (−42) gives 0010 1010 (42). Trace it bit by bit

Minimum and maximum without a branch

min = y ^ ((x ^ y) & -(x < y));
max = x ^ ((x ^ y) & -(x < y));

In this C, x and y are int8_t values.

The smaller and the larger of two signed integers, selected with a mask instead of an if.

x < y is 1 or 0 in C, so −(x < y) is either all ones or all zeros: a mask that selects. When it is all ones, (x ^ y) & mask is x ^ y, and y ^ (x ^ y) = x; when it is 0, y ^ 0 = y. So min is x exactly when x < y.

This version compares instead of subtracting, so it cannot overflow. Modern compilers often turn the plain if into a conditional move anyway, so measure before using it.

Example at 8 bits: x = 0101 1000 (88), y = −42 gives min = −42, max = 88. Trace it bit by bit

Average without overflow

(x & y) + ((x ^ y) >> 1)

In this C, x and y are uint8_t values.

The average of two unsigned integers, rounded down, without x + y overflowing.

Addition splits into the carries and the sum without carries: x + y = 2(x & y) + (x ^ y). The bits in both numbers are counted twice and the bits in exactly one are counted once. Halving each part separately gives (x & y) + ((x ^ y) >> 1), and no intermediate value is larger than the result.

The obvious (x + y) / 2 fails as soon as x + y no longer fits: the carry out of the top bit is lost before the division. A real case was a binary search midpoint, (low + high) / 2, which Joshua Bloch reported in 2006 as a bug in Java’s Arrays.binarySearch for arrays of more than about a billion elements.

Example at 8 bits: x = 1100 1000 (200), y = 100 gives 1001 0110 (150). Trace it bit by bit

Modulo a power of two

/* x % n, for n a power of two */
x & (n - 1)

In this C, x and n are uint8_t values.

The remainder of x divided by n, for an unsigned x and a power of two n, with an AND instead of a division.

Dividing by 2^k shifts the bits right by k places, and the remainder is the k bits that fall off the end. n − 1 is a mask of exactly those k low bits (8 − 1 = 0b111), so AND keeps the remainder and drops the quotient.

It only works when n is a power of two; for any other n, n − 1 is not a block of low ones. For a negative signed x it gives a different answer from C’s %, which rounds towards zero and keeps the sign: −7 % 8 is −7, while −7 & 7 is 1. Java’s HashMap keeps its table size a power of two and picks a bucket with (n − 1) & hash.

Example at 8 bits: x = 0101 1101 (93), n = 8 gives 0000 0101 (5). Trace it bit by bit

Round up to the next power of two

x--;
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x++;

In this C, x is a uint8_t.

The smallest power of two that is greater than or equal to x.

After x−−, OR-ing x with itself shifted right by 1, 2, 4 and so on copies its highest 1 into every position below it: each step doubles the length of the run of 1s, so log2(width) steps fill them all. The result is 2^k − 1, and adding 1 carries all the way up to 2^k.

The decrement first is what makes an exact power of two come back unchanged: 64 − 1 = 63 fills to 63 and rounds up to 64. Two edge cases come from wrapping: x = 0 gives 0 rather than 1 (0 − 1 is all ones, and +1 wraps back to 0), and a value above the largest power of two that fits also wraps to 0.

Example at 8 bits: x = 0101 1000 (88) gives 1000 0000 (128). Trace it bit by bit

Reverse the bits

x = ((x >> 1) & 0x55) | ((x & 0x55) << 1);
x = ((x >> 2) & 0x33) | ((x & 0x33) << 2);
x = ((x >> 4) & 0x0F) | ((x & 0x0F) << 4);

In this C, x is a uint8_t.

Mirror the bit order, so bit 0 swaps with the top bit, bit 1 with the one below it, and so on.

Swap neighbouring bits, then neighbouring pairs, then nibbles, then bytes, until the two halves swap. Each line uses a mask that picks the lower field of every pair of fields: shifting right by s and masking moves the upper fields down, masking and shifting left moves the lower fields up, and OR puts them together.

Reversing every level of a binary tree of fields reverses the whole, in log2(width) steps instead of one step per bit.

Example at 8 bits: x = 0101 1000 (88) gives 0001 1010 (26). Trace it bit by bit

Binary to Gray code

x ^ (x >> 1)

In this C, x is a uint8_t.

The reflected binary Gray code of x, where counting up changes one bit at a time.

Each Gray code bit is the XOR of a binary bit and the bit above it, so it is 1 exactly where the binary number changes from one bit to the next. Shifting right by one lines every bit up with its upper neighbour, and one XOR does all the positions at once. The top bit is XORed with the 0 shifted in, so it stays as it is.

Going back is not one step: each binary bit is the XOR of the Gray bit in the same position and every Gray bit above it, which takes a loop or a shift-and-XOR cascade like the parity trick.

Example at 8 bits: x = 0101 1000 (88) gives 0111 0100 (116). Trace it bit by bit

Sign-extend a k-bit value

/* x holds a k-bit field */
m = 1u << (k - 1);
r = (x ^ m) - m;

In this C, x is an int8_t.

Widen a k-bit two's complement number to the full width, keeping its value.

A k-bit field from a packet or a register is negative when its bit k − 1 is set, but in a wider variable that bit is just a positive weight of 2^(k−1). XOR with m flips that bit, which is the same as adding 2^(k−1) when it was 0 and subtracting it when it was 1; subtracting m then takes 2^(k−1) away. A positive field comes back unchanged and a negative one ends up 2^k lower, which is its signed value, with the sign copied into every bit above.

The other common form shifts the field to the top and back: (int32_t)(x << (32 − k)) >> (32 − k). That relies on an arithmetic right shift; the XOR version only needs wrapping arithmetic, so it also works on unsigned types.

Example at 8 bits: x = 0000 1011 (11), k = 4 gives 1111 1011 (−5). Trace it bit by bit

Toggle ASCII letter case

c ^ 0x20   /* 'a' <-> 'A' */

In this C, c is a uint8_t.

Switch an ASCII letter between upper and lower case by flipping one bit.

ASCII puts the capitals at 0x41 to 0x5A and the small letters at 0x61 to 0x7A, exactly 0x20 apart, so the two cases of a letter differ only in bit 5. XOR with 0x20 flips it. c | 0x20 forces lower case and c & ~0x20 forces upper case.

Only letters have a partner: the same flip turns [ into { and @ into a back-quote, so check the character is a letter first. It does not apply to accented letters in UTF-8.

Example at 8 bits: x = 0110 0001 (97) gives 0100 0001 (65). Trace it bit by bit