Bit Manipulation Idioms Worth Knowing

Part II · Module 15 · Chapter 15.7 · Bit Manipulation Idioms Worth Knowing

1. Why Learn These at All

Not for speed. Chapter 14.4 measured three different ways of reading four bytes compiling to the same single instruction, and the same thing is true here: a compiler recognises x & (x - 1) and x / 4 and emits whatever the target does best. Writing the clever form rarely changes the output and sometimes makes it worse.

The reason is reading. These expressions appear in driver code, in reference models, in vendor headers and in code review, written by people who were not thinking of them as clever at all. An unfamiliar one stops you for ten minutes; a familiar one is as transparent as a loop. That is the whole return, and it is enough.

Every idiom below is measured, and every one is explained — because an idiom you have memorised without understanding is one you will apply in the one case where it does not hold.

2. Is It a Power of Two?

static int is_pow2(uint32_t x) { return x != 0u && (x & (x - 1u)) == 0u; }

is_pow2 : 0:0 1:1 2:1 3:0 1024:1 0x80000000:1

Why it works. A power of two has exactly one bit set. Subtracting 1 from it clears that bit and sets every bit below — 1000 becomes 0111 — so the two have no bits in common and the AND is zero. For anything with two or more bits set, the bits above the lowest one survive the subtraction unchanged, so the AND keeps them and is non-zero.

The x != 0 matters. For zero, x - 1 is 0xFFFFFFFF (unsigned wraparound, well defined by Chapter 13.4) and 0 & 0xFFFFFFFF is 0 — so without the guard, zero reports as a power of two. Whether you want that depends on the caller: an alignment check usually does not, a "single bit set?" check usually does not either. Decide and write it down.

Where you meet it: validating an alignment argument, checking that a DMA burst size is legal, confirming exactly one interrupt source is pending.

3. Isolate and Clear the Lowest Set Bit

static uint32_t lowest_set(uint32_t x)   { return x & (~x + 1u); }
static uint32_t clear_lowest(uint32_t x) { return x & (x - 1u);  }

lowest_set(0xB0)   = 0x10
clear_lowest(0xB0) = 0xa0

0xB0 is 1011 0000. Its lowest set bit is bit 4, so isolating gives 0x10 and clearing gives 0xA0.

Why lowest_set works. ~x + 1 is the two's complement negation. Negating flips every bit above the lowest set bit and leaves the lowest set bit and the zeros below it unchanged — so x and -x agree in exactly one place.

You will more often see it written x & -x, and on an unsigned operand that is the same thing and is well defined: unary minus on an unsigned value is 2ⁿ − x, ordinary wraparound rather than anything exotic. Measured, the two forms agree for every value from 0 to 69999:

lowest_set(0xB0)=0x10  lowest_neg(0xB0)=0x10  agree:1
agree over 0..69999: yes

Write whichever your codebase uses. ~x + 1u is marginally clearer about being deliberate; x & -x is what you will meet.

clear_lowest is the loop you actually want. Iterating set bits by shifting through all 32 positions costs 32 iterations whatever the input; this costs one per set bit:

while (pending != 0u) {
    uint32_t bit = lowest_set(pending);
    handle_irq(ctz32(bit));            /* ctz32 is §5 */
    pending = clear_lowest(pending);
}

That is the standard shape of an interrupt dispatch loop, and recognising it is most of the reason to read this chapter.

4. Round Up to a Multiple

static uint32_t align_up(uint32_t x, uint32_t a) { return (x + a - 1u) & ~(a - 1u); }

align_up(1000, 64)  = 1024
align_up(1024, 64)  = 1024
align_up(0, 64)     = 0

Why it works, in two halves. ~(a - 1) is the mask that clears the low bits — for a = 64, a - 1 is 0x3F and ~0x3F is 0xFFFFFFC0, so ANDing rounds down to a multiple of 64. Adding a - 1 first pushes any value that is not already a multiple up past the next one, so the round-down lands on it. A value that is already aligned is pushed to just below the next multiple and rounds back down to itself, which is why align_up(1024, 64) is 1024 rather than 1088.

It requires a to be a power of two — §2's test is the precondition — because otherwise ~(a - 1) is not a run of low zeros and means nothing. An assertion says so:

assert(is_pow2(a));

Where you meet it: DMA buffer sizing, cache-line padding, page rounding, laying out a structure in a memory map.

5. Counting Bits and Finding Them

These are the ones with hardware instructions behind them, and C17 has no standard way to reach them.

__builtin_popcount(x)   /* how many bits are set            */
__builtin_clz(x)        /* count leading zeros,  from bit 31 */
__builtin_ctz(x)        /* count trailing zeros, from bit 0  */

__builtin_popcount(0xB0) = 3
__builtin_clz(0xB0)      = 24
__builtin_ctz(0xB0)      = 4

0xB0 has three bits set; its highest is bit 7, so there are 24 zeros above it; its lowest is bit 4, so four below.

clz and ctz are how you turn a bit mask back into a bit number — ctz(lowest_set(pending)) is the index of the lowest pending interrupt — which is the other half of §3's dispatch loop.

These are compiler extensions, not ISO C: Chapter 1.3's category. GCC and clang both provide them; MSVC spells them __popcnt and _BitScanReverse. C23 standardises the whole family in <stdbit.h>, which would be the right answer — except that it is not available here:

$ cc -std=c2x sb.c
sb.c:1:10: fatal error: 'stdbit.h' file not found

So on this platform the builtins are the practical route, and like any extension they belong behind a small wrapper rather than scattered through the code.

6. Two More You Will Meet

Swap bytes. Chapter 14.3 measured __builtin_bswap32(0x11223344) as 0x44332211, and measured the portable shift form compiling to the same single rev instruction. Use the shift form for serialisation; recognise the builtin when you read it.

Create a mask of the low n bits. (UINT32_C(1) << n) - 1u, which is Chapter 15.2 §4 — and its edge at n == 32 is the one every reader of this module should now see coming.

Conditionally set or clear without branching:

reg = (reg & ~MASK) | (-(uint32_t)flag & MASK);

-(uint32_t)flag is 0xFFFFFFFF when flag is 1 and 0 when it is 0, so the second term is MASK or nothing. It appears in code that wants no branch, and it is worth recognising — though a plain if is clearer and the compiler usually generates the same thing. If you write it, note that it depends on flag being exactly 0 or 1, which is Chapter 15.3 §5's !! idiom earning its place.

7. The Misconception: These Are Optimisations

"Writing x & (x - 1) instead of a loop makes the code faster."

Sometimes, and almost never for the reason people think, and it is the wrong thing to optimise for.

The compiler already knows these transformations. It turns division by a constant power of two into a shift, recognises population-count loops, and lowers __builtin_popcount to a single instruction where the target has one and to a good sequence where it does not. Writing the idiom by hand usually produces identical output — Chapter 14.4 measured exactly that pattern for a different set of expressions.

Where an idiom genuinely wins is when it changes the algorithm, not the instruction. §3's dispatch loop is the real example: iterating set bits costs one iteration per set bit rather than one per bit position. On a 32-bit status register with two interrupts pending, that is 2 iterations against 32 — and no compiler will make that change for you, because it requires knowing that only set bits matter.

So the rule is:

• Reach for an idiom when it expresses the algorithm better — iterate set bits, round to an alignment, test a single-bit condition.
• Do not reach for one to replace arithmetic the compiler already handles. x / 4 on an unsigned value is clear and compiles to a shift; writing x >> 2 gains nothing and, for signed values, is a different operation entirely (Chapter 15.6 §6).

And the deliberately excluded category: there is a large literature of bit tricks — branchless absolute values, parity by XOR-folding, bit reversal by interleaved masks — that are genuinely ingenious and that you will essentially never meet in driver code. They are not here because the test for this chapter was will a reader encounter this written by someone else, and for those the answer is no. If you meet one, the way to read it is the way this chapter has read each of these: find the identity it depends on, then check the edges.

8. Module 15 in One Page

The module took the operators from Module 3 and the representation from Module 2 and turned them into the fluency register work needs. Every claim was measured on Apple clang 21 / arm64.

Three threads ran through all seven.

The failures live at the top bit. The width-32 mask, the promoted 0x8000, the sign bit of a 12-bit field, the complement of a narrow mask — every one of them is correct for small values and wrong at the edge. Testing with representative data finds none of them.

Almost nothing diagnoses them. The ~ trap passed -Weverything. The width-32 shift passed every warning flag. The dropped reserved bit passed everything, because it is not an error at all — it is a correct program disagreeing with a document. Only UBSan caught the two that were genuinely undefined, which is Chapter 13.10's measured ceiling arriving again.

Precision about status mattered more than caution. Three separate things in this module are routinely mislabelled: 1u << 32 is undefined, the sign-extension shift trick is implementation-defined, and truncation on assignment is fully defined. Treating all three as "dangerous" would have been useless. Knowing which is which is what tells you whether to add a guard, a _Static_assert, or nothing at all.

9. What Comes Next

Every register in this module has been a uint32_t variable. It held a value, you extracted fields from it, you wrote fields back into it, and it did exactly what a variable does.

A real register is not a variable. Reading it may change it. Writing it may do something other than store. Its value may change between two reads with no code of yours in between. And a loop that polls it — written with everything this module teaches, and correct in every detail of its masks and shifts — can be removed entirely by the optimiser, because nothing in the C the compiler sees says the value could change.

Module 16, Registers and Memory-Mapped I/O, is the full path from a C statement to RTL state: a store issued by software, an address decoded through the interconnect, a peripheral register responding, hardware behaviour changing. It traces that path (16.1), reads an address map and computes register addresses from bases and offsets (16.2), performs the access itself at the right width through a typed pointer (16.3), applies this module's masks and shifts to a real register description (16.4), does read-modify-write where the intermediate state is visible to hardware (16.5), and then deals with the registers that break the assumptions quietly held throughout this module — the ones that are read-only, or write-one-to-clear, or that do not read back what was written (16.6).

Its prerequisites are stated plainly in the curriculum: pointers, widths, alignment and bit fields — all already taught. Module 14 supplied the first three; this module supplied the fourth. Chapter 14.6 stopped at the address and said why. Module 16 is where the address and the fields meet.

10. What You Should Be Able to Say Now

1. The reason to learn an idiom is to read it, not for speed — the compiler already knows these transformations.
2. x && (x & (x-1)) == 0 tests a power of two. The zero guard matters: 0 & 0xFFFFFFFF is 0, so zero reports true without it.
3. x & -x isolates the lowest set bit; x & (x-1) clears it. Measured agreeing with x & (~x+1) for every value tested. Unary minus on unsigned is defined wraparound.
4. The dispatch loop — isolate, handle, clear — costs one iteration per set bit instead of one per bit position. That is a real algorithmic win no compiler will make for you.
5. (x + a - 1) & ~(a - 1) rounds up to a power-of-two multiple, and requires a to be a power of two. Measured: 1000→1024, 1024→1024, 0→0.
6. popcount, clz, ctz are compiler extensions, not ISO C. C23's <stdbit.h> is the standard answer and is not available on this platform.
7. __builtin_clz(0) is documented undefined and returned 32 at -O0, -O1, -O2 and when folded. A consistent answer is not a guarantee. Wrap it, and decide what your function returns for zero.
8. An idiom earns its place by expressing the algorithm, not by replacing arithmetic the compiler already handles.

11. Exercises

1. Implement is_pow2 and test 0, 1, 2, 3, 1024 and 0x80000000. Then remove the zero guard and say which single input changes.
2. Write the interrupt dispatch loop from §3 using lowest_set, ctz32 and clear_lowest. Count its iterations for a status word with 2 bits set, and compare against the shift-through-32-positions version.
3. Verify that x & -x and x & (~x + 1u) agree for every uint16_t value. Say why the exhaustive test is feasible here and what you would do for uint32_t.
4. align_up(x, a) requires a to be a power of two. Call it with a = 100 and explain the result from the definition of ~(a - 1).
5. Reproduce the __builtin_clz(0) measurement at three optimisation levels. Then write clz32 three ways — returning 32, returning −1, and asserting — and say which you would put in a driver and why.
6. Write §6's branchless conditional set. Then write the plain if version, compile both at -O2 -S, and compare. Report what you found.
7. Find a bit expression in any real codebase you have access to that you did not immediately understand. Identify the identity it depends on and the edge case it assumes away. If it turns out to be one of this chapter's, say which.

12. Summary

• Learn these to read them. The compiler already does the transformations; the win is comprehension.
• x && (x & (x-1)) == 0 — power of two. Guard zero.
• x & -x isolates the lowest set bit, x & (x-1) clears it; measured identical to x & (~x+1u). Unsigned unary minus is defined wraparound.
• The dispatch loop costs one iteration per set bit — a genuine algorithmic improvement, unlike most bit tricks.
• (x + a - 1) & ~(a - 1) rounds up; a must be a power of two. Measured 1000→1024, 1024→1024, 0→0.
• popcount/clz/ctz are extensions; C23's <stdbit.h> is not available here.
• __builtin_clz(0) returned 32 at every optimisation level and is documented undefined. Wrap it and choose your own answer.
• Reach for an idiom when it expresses the algorithm, not to outguess the optimiser.