C Bit Utility Functions: Popcount, Trailing Zeros Count, Reverse All Bits

Question

Here are some utility bitwise functions for 64 bit integers. I have independently derived inv64 (inverse all bits) and pcnt64 (count bits set to 1) myself, though I am sure someone else has before, so this is nothing new. But ctz64 (count trailing zero bits) is a modified version of Count the consecutive zero bits (trailing) on the right in parallel (Bit Twiddling Hacks).

uint64_t inv64(uint64_t n) {
    n = (n & 0x5555555555555555ULL) << 1 | n >> 1 & 0x5555555555555555ULL;
    n = (n & 0x3333333333333333ULL) << 2 | n >> 2 & 0x3333333333333333ULL;
    n = (n & 0xF0F0F0F0F0F0F0FULL) << 4 | n >> 4 & 0xF0F0F0F0F0F0F0FULL;
    n = (n & 0xFF00FF00FF00FFULL) << 8 | n >> 8 & 0xFF00FF00FF00FFULL;
    n = (n & 0xFFFF0000FFFFULL) << 16 | n >> 16 & 0xFFFF0000FFFFULL;
    return n << 32 | n >> 32;
}
uint8_t pcnt64(uint64_t n) {
    n = (n & 0x5555555555555555ULL) + (n >> 1 & 0x5555555555555555ULL);
    n = (n & 0x3333333333333333ULL) + (n >> 2 & 0x3333333333333333ULL);
    n = (n & 0xF0F0F0F0F0F0F0FULL) + (n >> 4 & 0xF0F0F0F0F0F0F0FULL);
    n = (n & 0xFF00FF00FF00FFULL) + (n >> 8 & 0xFF00FF00FF00FFULL);
    n = (n & 0xFFFF0000FFFFULL) + (n >> 16 & 0xFFFF0000FFFFULL);
    return (uint8_t)n + (uint8_t)(n >> 32);
}
uint64_t ctz64(uint64_t n) {
    n &= -(int64_t)n;
    return (!(n & 0xFFFFFFFFULL) << 5 |
            !(n & 0xFFFF0000FFFFULL) << 4 |
            !(n & 0xFF00FF00FF00FFULL) << 3 |
            !(n & 0xF0F0F0F0F0F0F0FULL) << 2 |
            !(n & 0x3333333333333333ULL) << 1 |
            !(n & 0x5555555555555555ULL)) + !n;
}

Answer 1

These look familiar to me, but they are apparently "different enough" that GCC and Clang fail to recognize them as idioms. Well, the bit-reversal comes out about as well as can be expected on x64 (GCC and Clang both managed to use bswap), but not the other two.

If I make a couple of changes to pcnt64 then suddenly GCC and Clang recognize it:

uint8_t pcnt64(uint64_t n) {
    n = n - ((n >> 1) & 0x5555555555555555ULL);
    n = (n & 0x3333333333333333ULL) + (n >> 2 & 0x3333333333333333ULL);
    n = (n + (n >> 4)) & 0xF0F0F0F0F0F0F0FULL;
    return (n * 0x0101010101010101ULL) >> 56;
}

Gets compiled into

popcnt64:
        xor     eax, eax
        popcnt  rax, rdi
        ret

Although when compiling with a different compiler and/or targeting a different platform, this can work out poorly - for example on an embedded platform that lacks both a built-in popcnt instruction and also a hardware multiplier. As is commonly the case, the same code is not the best for all platforms. You could do some #ifdef-based selection between alternative implementations, or just decide which platforms you care about the most.

I don't know what portable code to write such that a tzcnt instruction comes out. If you don't care about portability so much, there's _tzcnt_u64 (from immintrin.h) which is at least "portable across compilers", though not across different CPUs. As a "dual" to that there is __builtin_ctzll which is a GCC/Clang builtin (maybe seen in some other random compilers, but not MSVC) but supported across different CPUs (note that it does not deal gracefully with the case where the input is zero).

In n &= -(int64_t)n; you should not be casting to int64_t to do the negation. Paradoxically that creates the potential for UB, while negating an unsigned integer is completely safe (with no edge cases) and does exactly what you need it to do. Though to silence some incorrect warnings, you may need to subtract from zero instead of negate.

There is an alternative trailing-zero-counting strategy that may be better in some cases (popcnt instructions are more widely available across different CPUs, and seem to be easier to get out of a compiler too): make a mask of the trailing zeroes and then popcnt that. For example:

uint64_t ctz64(uint64_t n) {
    return pcnt64(~n & (n - 1));
}

~n & (n - 1) is a trailing-bit-manipulation idiom, see manipulating rightmost bits.

Clang even managed to make a tzcnt from that; GCC's more literal interpretation is not bad either.

Answer 2

Small stuff:

---

Missing include

Add #include <stdint.h>.

Inverse?

Rather than inverse, which can sound like a bit-wise complement, consider bit_reverse or the like.

// inv64()
bit_reverse64()

What the LL?

Minor: None of constants need the LL suffix in OP's code as all are & masks with a uint64_t.
The U remains useful to avoid mixed sign-ness is the operations.

Today long long is commonly 64-bit. It maybe wider in the future.

With fixed width types, when wanting to insure a constant accommodates a certain width, code can use (U)INTN_C as in UINT64_C(0xFFFFFFFF).

Minor: ()

Consider Use some parentheses. >> and & besides each other is to me as good as a bug. .

Not needed if the anticipated readers of code know the C's order of precedence rules well.
After many decades, I still need to review the levels (15) from time-to-time for the less popular precedence rules.

Minor: Why 2 casts?

I suspect a good compiler will emit efficient code either way.

(uint8_t)n + (uint8_t)(n >> 32);
vs.
(uint8_t) (n + (n >> 32));

Note that with (uint8_t)n + (uint8_t)(n >> 32), Both (uint8_t) operands of the + are converted to unsigned before the addition. The final sum then incurs a silent (uint8_t) on the return which may warn on some pedantic compilers.