Introduction

Finding the position of the highest set bit is a common building block in low-level code such as allocators, hash tables, compression routines, and numeric utilities. In modern C, the fastest answer is usually “use the compiler intrinsic that maps to a native CPU instruction, and guard the zero case explicitly.” A portable loop still has value as a fallback, but it is rarely the best hot-path implementation when intrinsic support is available.

Define the Contract Before Optimizing

Before worrying about speed, decide what the function should return. The usual and practical convention is:

• input type is unsigned
• result is a zero-based bit index
• input 0 returns -1

That contract avoids signed-shift surprises and gives callers a consistent answer for the one ambiguous case.

For example, if the value is 18, which is binary 10010, the highest set bit is at index 4.

Fast Path on GCC and Clang

GCC and Clang expose builtins that count leading zeros. Once you know the width of the type, the most significant bit index follows directly.

1#include <limits.h>
2
3int msb_index_u32(unsigned int x) {
4    if (x == 0) {
5        return -1;
6    }
7    return (int)(sizeof(unsigned int) * CHAR_BIT - 1 - __builtin_clz(x));
8}
9
10int msb_index_u64(unsigned long long x) {
11    if (x == 0) {
12        return -1;
13    }
14    return (int)(sizeof(unsigned long long) * CHAR_BIT - 1 - __builtin_clzll(x));
15}

This is usually the right default because the compiler can lower the builtin to efficient hardware instructions on supported targets.

The critical detail is the zero guard. Calling __builtin_clz or __builtin_clzll with zero is undefined behavior.

MSVC Uses Bit-Scan Intrinsics

If you are compiling with MSVC, the usual equivalents are _BitScanReverse and _BitScanReverse64.

1#if defined(_MSC_VER)
2#include <intrin.h>
3
4int msb_index_u32_msvc(unsigned int x) {
5    unsigned long index;
6    if (_BitScanReverse(&index, x)) {
7        return (int)index;
8    }
9    return -1;
10}
11
12int msb_index_u64_msvc(unsigned long long x) {
13    unsigned long index;
14    if (_BitScanReverse64(&index, x)) {
15        return (int)index;
16    }
17    return -1;
18}
19#endif

The surrounding wrapper is worth it because the call sites should not need to care which compiler-specific primitive produced the answer.

Portable Fallbacks Still Matter

When intrinsics are unavailable or portability is more important than the last fraction of performance, a shift-based fallback is completely reasonable.

1int msb_index_loop(unsigned int x) {
2    int pos = -1;
3    while (x != 0) {
4        x >>= 1;
5        pos++;
6    }
7    return pos;
8}

This is easy to verify and works everywhere, but it does more iterations than intrinsic-backed code on large values.

A branchy binary-search-style fallback reduces the number of steps.

1int msb_index_binary(unsigned int x) {
2    int pos = 0;
3
4    if (x == 0) {
5        return -1;
6    }
7    if (x >= (1u << 16)) {
8        x >>= 16;
9        pos += 16;
10    }
11    if (x >= (1u << 8)) {
12        x >>= 8;
13        pos += 8;
14    }
15    if (x >= (1u << 4)) {
16        x >>= 4;
17        pos += 4;
18    }
19    if (x >= (1u << 2)) {
20        x >>= 2;
21        pos += 2;
22    }
23    if (x >= (1u << 1)) {
24        pos += 1;
25    }
26
27    return pos;
28}

This is a good portability option when you want predictable behavior without compiler-specific hooks.

Measure in Context, Not in Theory

It is easy to overstate the importance of this helper. If the function is not on a hot path, a simple portable version may be perfectly adequate. If it is hot, benchmark the exact build, platform, and input distribution you care about.

Things that affect the real answer include:

• whether the compiler inlines the helper
• the distribution of zero and nonzero inputs
• branch prediction behavior in fallback code
• target CPU instruction support

In other words, “fastest” is partly a tooling question, not only an algorithm question.

Keep the Helper Narrow and Testable

Bit utilities age badly when every file invents its own variant. Put one implementation behind a clear function name, test the edge cases, and reuse it.

Simple tests are enough to catch most mistakes.

1#include <assert.h>
2
3int main(void) {
4    assert(msb_index_u32(0) == -1);
5    assert(msb_index_u32(1) == 0);
6    assert(msb_index_u32(2) == 1);
7    assert(msb_index_u32(18) == 4);
8}

That small test set already verifies the contract and protects against off-by-one errors.

Common Pitfalls

• Calling leading-zero intrinsics with 0, which is undefined for the GCC and Clang builtins.
• Using signed integers and then getting surprising results from shifts or promotions.
• Mixing one-based and zero-based bit positions across different modules.
• Writing only a 32-bit implementation and silently truncating 64-bit inputs.
• Chasing micro-optimizations before confirming that this helper is actually performance-critical.

Summary

• On modern compilers, an intrinsic-backed implementation is usually the fastest practical answer.
• Guard zero input explicitly before using builtins such as __builtin_clz.
• Provide compiler-specific wrappers so the rest of the code stays clean.
• Keep a portable fallback for compatibility or low-dependency builds.
• Decide the contract first, then optimize the implementation that matches it.