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:
Post a Comment