Leading and trailing zeros

Overview

Counting the zeros before the first 1 bit answers questions like "what is the highest power of two in this value?" and "how many times does this divide by two?". Count leading zeros (CLZ) counts from the most-significant end down to the highest set bit; count trailing zeros (CTZ) counts from the least-significant end up to the lowest set bit. Both share one awkward input: zero has no set bit at all, so there is no natural answer. The convention used here is to return the full width (32), and whatever convention you choose, it must be handled explicitly — the hardware instructions behind these operations leave the zero case undefined.

Why it matters

CLZ gives you the integer base-2 logarithm, which sizes buckets in allocators, picks the level in a skip list, and computes how many bits a value needs. CTZ gives you the index of the lowest set bit, which turns the isolate-and-strip loop into an iteration over bit indices. And the zero case matters: __builtin_clz(0) is undefined behaviour, and a memory allocator that trips over it on a zero-size request has a real bug.

Core concepts

Leading zeros. Test the top bit (x & 0x80000000u); while it is clear, shift left and count. When the loop ends, the count is the number of zeros above the highest set bit. clz(1) is 31; clz(0x80000000) is 0.

Trailing zeros. Test the bottom bit (x & 1u); while it is clear, shift right and count. ctz(1) is 0; ctz(8) is 3.

The zero case is the whole problem. With no set bit, both loops would run forever (or the hardware instruction's result is undefined). Handle x == 0 first, before the loop, and document the value you return — 32 is the common choice.

Relationship to logarithms. 31 - clz(x) is the index of the highest set bit, i.e. floor(log2(x)) for non-zero x. That is how you size a value in bits.

Relationship to isolate. ctz(x) is the index of the bit that x & -x isolates — the value-to-index conversion mentioned in that lesson.

Compiler intrinsics. __builtin_clz/__builtin_ctz map to single instructions but are GNU extensions undefined for zero. Portable code writes the loop or wraps the intrinsic with a zero check.

Syntax notes

#include <stdint.h>

int clz(uint32_t x) {                 // leading zeros
    if (x == 0) return 32;            // handle first — no set bit exists
    int n = 0;
    while (!(x & 0x80000000u)) { n++; x <<= 1; }
    return n;
}

int ctz(uint32_t x) {                 // trailing zeros
    if (x == 0) return 32;
    int n = 0;
    while (!(x & 1u)) { n++; x >>= 1; }
    return n;
}

/* floor(log2(x)) for x != 0 */
int ilog2(uint32_t x) { return 31 - clz(x); }

Key points:

• The x == 0 guard must come before the loop, or it never terminates.
• 0x80000000u is the top-bit mask for 32 bits; match it to your width.
• __builtin_clz(0) / __builtin_ctz(0) are undefined — never call them unguarded.

Lesson

Leading zeros count the 0 bits above the highest set bit; trailing zeros count them below the lowest. Both return 32 for an all-zero word. 32 - clz(x) is the bit-length (position of the top set bit); ctz(x) is the exponent of the largest power of two dividing x.

The demo reports both for a sample value.

Code examples

#include <stdio.h>
#include <stdint.h>
static int clz(uint32_t x){ if(!x) return 32; int n=0; while(!(x&0x80000000u)){n++;x<<=1;} return n; }
static int ctz(uint32_t x){ if(!x) return 32; int n=0; while(!(x&1u)){n++;x>>=1;} return n; }
int main(void){
    uint32_t x = 0x00F00000u;
    printf("x = 0x%08X\n", x);
    printf("leading zeros  = %d\n", clz(x));
    printf("trailing zeros = %d\n", ctz(x));
    printf("bit length     = %d\n", 32 - clz(x));   /* position of highest set bit + 1 */
    return 0;
}

Line by line

Common mistakes

Infinite loops or wrong counts when x==0 isn't special-cased.

Debugging tips

Compiler errors and warnings:

• No warning at all for the missing zero guard — the compiler cannot see the infinite loop. This one is caught by testing, not by the compiler.
• warning: left shift count >= width of type if you hand-roll a mask with the wrong width.

Runtime symptoms:

• The program hangs. You passed 0 and there is no guard — the classic failure.
• clz is off by one. Remember clz(1) is 31, not 32; the count is of zeros above the highest set bit.
• Wrong results for large values. You used a signed int; x <<= 1 on a signed value with the top bit set is overflow (undefined). Use uint32_t.
• Works locally, crashes elsewhere. You used __builtin_clz and something passed zero. Wrap it.

Technique: test 0, 1, 0x80000000 and 0xFFFFFFFF first — those four pin down both conventions and the guard.

Memory safety

• The zero case is undefined for the intrinsics. __builtin_clz(0) and __builtin_ctz(0) have no defined result; the compiler may assume the input is non-zero and optimise accordingly. Always guard, even if it "seems to return 32" on your machine.
• Infinite loop on zero. In the hand-written versions the missing guard is a hang, not a crash — a denial of service if the value comes from input.
• Signed shifting. x <<= 1 on a signed value whose top bit is set is undefined; x >>= 1 on a negative signed value sign-extends and the trailing-zero loop never terminates. Use unsigned types.
• Width assumptions. The 32 return convention and the 0x80000000u mask are tied to a 32-bit type; a 64-bit version needs 64 and 0x8000000000000000u.
• As an array index. 31 - clz(x) is a valid index only for non-zero x; sizing an allocator bucket from a zero request must be handled before indexing.

Real-world uses

Concrete uses: Memory allocators use CLZ to pick a size-class bucket in constant time. printf-style number formatting uses it to size a buffer. Network stacks compute prefix lengths for routing tables. The Linux kernel's fls/ffs helpers are these operations. Priority queues built on bitmaps use CTZ to find the highest-priority pending task in one step.

Professional best practices:

Beginner:

• Write the zero guard before you write the loop.
• Document the convention you chose for zero in a comment — 32 is common but not universal.

Intermediate:

• Prefer a guarded wrapper around __builtin_clz/__builtin_ctz in performance-sensitive code, falling back to the loop for portability.
• Derive the width from sizeof(x) * CHAR_BIT rather than hard-coding 32 in a header used by several types.
• Validate any intrinsic-based version against the simple loop over random inputs including the boundary values.

Practice tasks

1. (Beginner) Implement clz and ctz. Both with the x == 0 guard returning 32. Example: clz(1) → 31, ctz(8) → 3, clz(0) → 32. Concepts: directional loops, the zero convention.

2. (Beginner) Integer log2. Implement int ilog2(uint32_t x) as 31 - clz(x), returning -1 for zero. Example: ilog2(1024) → 10. Concepts: highest-set-bit index.

3. (Intermediate) Bits required. Implement int bits_needed(uint32_t x) returning how many bits are needed to represent x (0 → 1, 255 → 8, 256 → 9). Concepts: CLZ applied to sizing.

4. (Intermediate) Index iteration. Rewrite the set-bit iteration from the isolate lesson to print indices using ctz, and confirm it matches a 32-position scan. Concepts: combining isolate/strip with CTZ, oracle testing.

Summary

CLZ counts zeros above the highest set bit and CTZ counts zeros below the lowest, giving you floor(log2(x)) and the index of the lowest set bit respectively. Zero is the case that decides whether your implementation is correct: it has no set bit, the naive loops would spin forever, and the compiler intrinsics __builtin_clz/__builtin_ctz are explicitly undefined for it — so guard it first and document the convention (32 here). Keep the value unsigned so shifting neither overflows nor sign-extends, and match the width constants to the type.

Practice with these exercises

• Count leading zeros
• Count trailing zeros