Example: Bitwise Log2 on Integers

Example: Bitwise Log2 on Integers

Calculating the base-two logarithm of integers can be quite useful. There are various algorithms that use logarithms in AI.

Let's calculate the integer logarithm of an integer. This means we aren't doing the proper fractional logarithm of a number, but we are truncating it down to the nearest integer. For example, log2(7) will be truncated to 2, rather than 2.807. Note that we're assuming the input is unsigned numbers, since logarithms of negatives are undefined. Also, we have to decide how to handle zero, because log2(0) is undefined (or negative infinity if you prefer).

A simple way to implement a truncated integer log2 function is to use floating-point functions and type casts back to int:

    int aussie_log2_integer_slow(unsigned int u)  
    {
        // Slow float-to-int version
        return (int)log2f(u);
    }

This works, but it's inefficient to use floating-point arithmetic on integers. Surely there's a faster way?

After some thoughts about binary bits, we notice that log2 of an integer is just the index position of the highest bit in a number. The log2 of 1 is 0, because the '1' is in position 0. The log2 of 2 (binary 10) is 1 because the leftmost 1 is in position 1. The log2 of 4 (binary 100) is 2, where the 1 is in index 2. The number 7 is binary 111, so log2 is the position of the leftmost 1, which is position 2. So, log2(7) is the same as log2(4), but log2(8) is 3.

There are numerous builtin bitwise functions that can find the leftmost set bit. With sudden insight, we note that we can use “CLZ” (count leading zeros) to compute how many prefix zeros there are before the leftmost 1 bit (i.e. counts the zeros up to the most-significant bit from the left). We can then compute the bit index position from the right in a 32-bit integer as “32-CLZ”. It's on the right track, and a bit of testing shows that the formula to use is “32-CLZ-1”.

Here's some example code that uses this CLZ method to compute log2 of an integer. This works on Microsoft Visual Studio using the <intrin.h> header file to declare intrinsics.

    int aussie_log2_integer_clz_intrinsic(unsigned int u) 
    {
        // LOG2 using CLZ
        int clz = __lzcnt(u);  // Count leading zeros
        const int bits = 8 * sizeof(u);
        return bits - clz - 1;
    }

And here's the macro version for those who don't trust compilers to inline properly:

    #define AUSSIE_LOG2_LZCNT(u) \
     ((8 * sizeof(unsigned)) - (__lzcnt((unsigned)(u))) - 1)

And this is actually not optimal. We really should help the C++ optimizer by reordering this to move the “-1” subtraction operation next to the other constant, noting that “sizeof” is a compile-time constant expression in C++. Putting them together would make sure that the compiler correctly merges these operations using constant folding. On x86 implementations, the CLZ builtin functions are presumably using the x86 LZCNT or BSR assembler instructions, which are both similar and fast.

Bug alert! Note that you can't use “ffs” (find first set bit) for this log2 method, because it gives you the offset of the least-significant set bit (i.e. the rightmost bit rather than the leftmost bit). The other x86 instructions of TZCNT (Trailing Zeros Count) and BSF (Bit Scan Forward) are also incorrect.

• Next: • Up: Table of Contents • Buy: Generative AI in C++: Coding Transformers and LLMs

The new AI programming book by Aussie AI co-founders: AI coding in C++ Transformer engine speedups LLM models Phone and desktop AI Code examples Research citations Get your copy from Amazon: Generative AI in C++