Introduction

If the task is to compute max(ctz(x), ctz(y)), there usually is no meaningful general shortcut beyond computing both trailing-zero counts and taking the larger one. The useful optimization question is not "can I invent a clever identity," but "am I already using the fast machine instruction my compiler provides for ctz?"

What ctz Means

ctz stands for "count trailing zeros." It tells you how many zero bits appear at the least significant end of a nonzero integer before the first 1 bit appears.

Examples:

• 'ctz(8) is 3 because 8 in binary is 1000'
• 'ctz(12) is 2 because 12 in binary is 1100'
• 'max(ctz(8), ctz(12)) is 3'

Another way to say it is that ctz(n) is the exponent of the highest power of 2 dividing n.

The Straightforward Solution Is Usually Optimal

On modern compilers, the obvious approach is already very strong:

1#include <stdio.h>
2
3unsigned max_ctz(unsigned x, unsigned y) {
4    unsigned cx = __builtin_ctz(x);
5    unsigned cy = __builtin_ctz(y);
6    return cx > cy ? cx : cy;
7}
8
9int main(void) {
10    printf("%u\n", max_ctz(8u, 12u));
11    return 0;
12}

Built-ins such as __builtin_ctz are often mapped to a dedicated CPU instruction or something very close to it. That means the operation is already constant time with a very small constant factor.

Why Combined Bit Tricks Usually Fail

It is tempting to ask whether x | y, x & y, or some other combined expression can give the answer in one step. There are related identities, but they do not generally give max(ctz(x), ctz(y)) for arbitrary nonzero inputs.

For example:

• 'ctz(x | y) tends to reflect the smaller trailing-zero count, not the larger one'
• 'ctz(x & y) fails when the lowest set bits do not overlap and the result becomes zero'

Take x = 8 and y = 16:

• 'ctz(x) is 3'
• 'ctz(y) is 4'
• the correct answer is 4
• 'x | y is 24, and ctz(24) is 3'
• 'x & y is 0, which is unusable for many ctz primitives'

So there is no simple universal one-expression replacement for both ctz calls.

A Mathematical View

If you think in terms of the 2-adic valuation, ctz(n) is v2(n). Then:

max(ctz(x), ctz(y)) = v2(lcm(x, y))

That identity is mathematically correct for nonzero integers, but it is not a speed trick. Computing an lcm or related quantity does not beat two hardware-friendly trailing-zero counts in normal code.

It is useful conceptually, not practically.

Portable Fallback When No Built-In Exists

If your environment does not provide a built-in ctz, a loop works:

1unsigned portable_ctz(unsigned x) {
2    unsigned count = 0;
3    while ((x & 1u) == 0u) {
4        x >>= 1u;
5        count++;
6    }
7    return count;
8}
9
10unsigned max_ctz_portable(unsigned x, unsigned y) {
11    unsigned cx = portable_ctz(x);
12    unsigned cy = portable_ctz(y);
13    return cx > cy ? cx : cy;
14}

This is slower than a hardware instruction, but it still shows the correct algorithmic structure: compute both counts, then take the maximum.

The Real Place to Optimize

If this expression matters in a profiler, the win is often outside the expression itself:

• cache one result if one operand repeats,
• batch many values so the compiler can vectorize surrounding work,
• reduce the number of times the computation is needed,
• or restructure the algorithm so the maximum is implied by another invariant.

For example, if y is constant across a loop:

1unsigned cy = __builtin_ctz(y);
2
3for (size_t i = 0; i < count; ++i) {
4    unsigned cx = __builtin_ctz(values[i]);
5    unsigned result = cx > cy ? cx : cy;
6    /* use result */
7}

That saves repeated work where it actually matters.

Handle Zero Explicitly

Many ctz built-ins are undefined for zero inputs. If zero is possible, define the behavior yourself:

1unsigned safe_ctz32(unsigned x) {
2    if (x == 0u) {
3        return 32u;
4    }
5    return __builtin_ctz(x);
6}

Whether 32 is the right sentinel depends on your integer width and your problem definition. The important point is to handle zero deliberately rather than hoping the built-in does something useful.

Common Pitfalls

The biggest pitfall is spending time hunting for a magical algebraic shortcut when the compiler already emits a near-optimal instruction for ctz.

Another mistake is using identities based on | or & without testing edge cases. Those formulas often appear promising and then fail as soon as the lowest set bits differ.

Developers also sometimes benchmark the wrong thing. Two ctz calls plus one comparison are all constant-time operations, so surrounding loop structure and memory access often dominate runtime.

Finally, never ignore zero-handling rules. A mathematically neat expression is still wrong if the language primitive is undefined for one of your inputs.

Summary

• In general, the best solution is still max(ctz(x), ctz(y)) computed directly.
• Compiler built-ins are usually already close to hardware-optimal.
• Simple combined bitwise expressions do not reliably replace both ctz calculations.
• If performance matters, optimize the surrounding algorithm and data flow instead.
• Define zero-input behavior explicitly because many ctz primitives do not.