What is a fast way to compute the (long int) ceiling(log_2(i))
, where the input and output are 64-bit integers? Solutions for signed or unsigned integers are acceptable. I suspect the best way will be a bit-twiddling method similar to those found here, but rather than attempt my own I would like to use something that is already well tested. A general solution will work for all positive values.
For instance, the values for 2,3,4,5,6,7,8 are 1,2,2,3,3,3,3
Edit: So far the best route seems to be to compute the integer/floor log base 2 (the position of the MSB) using any number of fast existing bithacks or register methods, and then to add one if the input is not a power of two. The fast bitwise check for powers of two is (n&(n-1))
.
Edit 2: A good source on integer logarithms and leading zeroes methods is Sections 5-3 and 11-4 in Hacker's Delight by Henry S. Warren. This is the most complete treatment I've found.
Edit 3: This technique looks promising: https://stackoverflow.com/a/51351885/365478
log2(a) : This function is used to compute the logarithm base 2 of a. Displays more accurate result than log(a,2). Syntax : math. log2(a) Parameters : a : The numeric value Return Value : Returns logarithm base 2 of a Exceptions : Raises ValueError if a negative no. is passed as argument.
This algorithm has already been posted, but the following implementation is very compact and should optimize into branch-free code.
int ceil_log2(unsigned long long x) { static const unsigned long long t[6] = { 0xFFFFFFFF00000000ull, 0x00000000FFFF0000ull, 0x000000000000FF00ull, 0x00000000000000F0ull, 0x000000000000000Cull, 0x0000000000000002ull }; int y = (((x & (x - 1)) == 0) ? 0 : 1); int j = 32; int i; for (i = 0; i < 6; i++) { int k = (((x & t[i]) == 0) ? 0 : j); y += k; x >>= k; j >>= 1; } return y; } #include <stdio.h> #include <stdlib.h> int main(int argc, char *argv[]) { printf("%d\n", ceil_log2(atol(argv[1]))); return 0; }
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With