CLZ counts the number of consecutive zero bits starting from the most significant bit (MSB) of a word until the first set bit. For a 32-bit input, CLZ(0x80000000) = 0, CLZ(1) = 31, and CLZ(0x00FF0000) = 8. **Edge case — input 0:** There is no set bit, so the result is undefined for most hardware CLZ instructions (e.g. ARM `CLZ` actually returns 32, but x86 `BSR` is undefined for 0). A portable software implementation must explicitly decide what to return for 0; below it returns 32. **Binary-search implementation (the standard portable, branch-light approach).** Instead of shifting one bit at a time (32 iterations), we narrow the position of the highest set bit in `log2(32) = 5` steps. Each step asks "is the highest set bit in the top half of the remaining window?": ```c #include /* Returns 32 for n == 0; otherwise the count of leading zero bits. */ int clz32(uint32_t n) { if (n == 0u) { return 32; } int count = 0; if ((n & 0xFFFF0000u) == 0u) { count += 16; n <<= 16; } if ((n & 0xFF000000u) == 0u) { count += 8; n <<= 8; } if ((n & 0xF0000000u) == 0u) { count += 4; n <<= 4; } if ((n & 0xC0000000u) == 0u) { count += 2; n <<= 2; } if ((n & 0x80000000u) == 0u) { count += 1; } return count; } ``` This is O(log N) — five comparisons — versus the naive O(N) bit-by-bit loop. **De Bruijn sequence implementation (table-based, no branches in the hot path).** First "smear" all bits below the highest set bit down to fill a contiguous run of 1s (producing `2^(k+1) - 1`), then use a perfect-hash multiply by a de Bruijn constant to index a 32-entry table giving `log2`. CLZ is then `31 - log2`: ```c #include int clz32_debruijn(uint32_t n) { if (n == 0u) { return 32; } /* Smear: set every bit below the MSB. */ n |= n >> 1; n |= n >> 2; n |= n >> 4; n |= n >> 8; n |= n >> 16; /* n is now 2^(k+1) - 1; the de Bruijn constant/table map this smeared value directly to log2 -- do NOT isolate the top bit first. */ static const uint8_t debruijn_log2[32] = { 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31 }; int log2 = debruijn_log2[(uint32_t)(n * 0x07C4ACDDu) >> 27]; return 31 - log2; } ``` **Optimizations:** - Prefer the binary-search or de Bruijn form over the bit-by-bit loop: O(log N) / O(1) instead of O(N). - The de Bruijn table approach is fully branch-free after the zero check, which helps on pipelines without good branch prediction (typical of small MCUs). - If the compiler/target supports it, use `__builtin_clz` (GCC/Clang) which maps to a single hardware instruction; just remember `__builtin_clz(0)` is undefined. - Specialize the width — don't run a 32-bit algorithm on data you know is 8- or 16-bit. **Uses of CLZ:** - **Floating-point normalization:** finding how far to left-shift a mantissa so the leading 1 sits in the implicit/MSB position (essential in soft-float and fixed→float conversion). - **Fast integer log2 / MSB position:** `log2(n) = 31 - clz(n)`, used for bucket sizing, allocator size classes, and tree depth. - **Round up to next power of two:** `1u << (32 - clz(n - 1))`. - **Priority encoders / interrupt arbitration:** find the highest-priority pending bit in a bitmask in O(1). - **Fixed-point math:** computing scale/shift amounts for renormalization and reciprocal/division algorithms (Newton-Raphson seeding). - **Compression and bit-stream parsing:** counting run lengths and Golomb/Elias code lengths.

Low-Level C & Bit Tricks Interview Questions