Wednesday, January 19, 2022

Quick and Dirty Function to get Rounded Up Log2

 Here is a quick and dirty C/C++ function to return the rounded up log base 2 of any integer.

int ceil_log_base_2(int value) {
    int ones = 0;
    int shifts = 0;
    while (value > 0) {
        shifts++;
        if (1 & value)
            ones++;
        value = value >> 1;
    }
    return --shifts + (ones > 1 ? 1 : 0);
}

My buddy Rob jumped in and spun this one x86 assembly style:

int __builtin_popcount (unsigned int x);
int __builtin_clz (unsigned int x);

int rob_ceil_log_base_2 (int value) {
    return ((sizeof(int) * 8) - __builtin_clz (value)) +
        (__builtin_popcount(value) > 1 ? 1 : 0) - 1;
}

And if you prefer inline, Rob has you covered there too:

int __builtin_popcount (unsigned int x);
int __builtin_clz (unsigned int x);
#define rob_ceil_log_base_2(value) (int) (sizeof(value) * 8) - \     __builtin_clz (value) + (__builtin_popcount(value) > 1 ? 0 : -1)

No comments: