4
\$\begingroup\$

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;
}
\$\endgroup\$
4
  • 2
    \$\begingroup\$ Use some parentheses. >> and & besides each other is to me as good as a bug. \$\endgroup\$
    – gnasher729
    Nov 20, 2023 at 17:06
  • \$\begingroup\$ @gnasher729 +-*/ > >> > & > ^ > | \$\endgroup\$
    – CPlus
    Nov 20, 2023 at 17:10
  • 1
    \$\begingroup\$ Not an answer but you might find Bit Twiddling Hacks very useful and/or interesting. \$\endgroup\$
    – Pryftan
    Nov 20, 2023 at 17:25
  • 1
    \$\begingroup\$ @Pryftan I do. They were the inspiration for ctz64(). \$\endgroup\$
    – CPlus
    Nov 20, 2023 at 17:27

2 Answers 2

8
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ If you're going to #ifdef anything, you'd probably want to #ifdef __GNUC__ and define these as __builtin_popcountll and so on. GNU C __builtin_clzll / ctzll are for unsigned long long which is normally the same as uint64_t but you could check. More importantly, those functions produce an undefined result for an input of 0. (Not UB but not a guaranteed 64 like _tzcnt_u64 / _lzcnt_u64). That allows them to compile to a single bsf / bsr instruction without checking for 0, unlike C++20 std::countr_zero / countl_zero. (__builtin_clzll(x|1) caps it at 63) \$\endgroup\$ Nov 20, 2023 at 8:56
  • 2
    \$\begingroup\$ Without being compiler dependent: Check if __has_builtin is defined, then check #if __has_builtin (__builtin_popcountll). So compilers that are not GNUC can implement this as well. \$\endgroup\$
    – gnasher729
    Nov 20, 2023 at 17:09
  • \$\begingroup\$ harold, At a future time (n * 0x0101010101010101ULL) >> 56 may incur a 128-bit multiplication as long long may be 128-bit. OTOH, Should that occur, I hope such a machine to optimize to a speedier 64-bit multiplication given the uint84_t return type. (n * 0x0101010101010101U) >> 56 and (n * UINT64_C(0x0101010101010101)) >> 56 avoid a future 128 bit multiply. \$\endgroup\$ Nov 21, 2023 at 11:26
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.