This is effectively log base 2, but I do not have access to this functionality in the environment I'm in. Manually walking through the bits to verify them is unacceptably slow. If it were just 4 bits, I could probably index it and waste some space in an array, but with 64 bits it is not viable.
Any clever constant time method to find which bit is set ? (The quantity is a 64-bit number).
EDIT: To clarify, there is a single bit set in the number.
I assume you want the position of the most significant bit that is set. Do a binary search. If the entire value is 0, no bits are set. If the top 32 bits are 0, then the bit is in the bottom 32 bits; else it is in the high half. Then recurse on the two 16-bit halves of the appropriate 32 bits. Recurse until you are down to a 4-bit value and use your look-up table. (Or recurse down to a 1-bit value.) You just need to keep track of which half you used at each recursion level.
The fastest method I know of uses a DeBruijn Sequence.
Find the log base 2 of an N-bit integer in O(lg(N)) operations with multiply and lookup
Note that in lg(N), N is the number of bits, not the number of the highest set bit. So it's constant time for any N-bit number.
If you know that the number is an exact power of 2 (i.e. there is only 1 bit set), there is an even faster method just below that.
That hack is for 32 bits. I seem to recall seeing a 64 bit example somewhere, but can't track it down at the moment. Worst case, you run it twice: once for the high 32 bits and once for the low 32 bits.
If your numbers are powers of 2 and you have a bit count instruction you could do:
bitcount(x-1)
e.g.
x x-1 bitcount(x-1)
b100 b011 2
b001 b000 0
Note this will not work if the numbers are not powers of 2.
EDIT
Here is a 64bit version of the De Brujin method:
static const int log2_table[64] = {0, 1, 2, 7, 3, 13, 8, 19, 4, 25, 14, 28, 9, 34,
20, 40, 5, 17, 26, 38, 15, 46, 29, 48, 10, 31,
35, 54, 21, 50, 41, 57, 63, 6, 12, 18, 24, 27,
33, 39, 16, 37, 45, 47, 30, 53, 49, 56, 62, 11,
23, 32, 36, 44, 52, 55, 61, 22, 43, 51, 60, 42, 59, 58};
int fastlog2(unsigned long long x) {
return log2_table[ ( x * 0x218a392cd3d5dbfULL ) >> 58 ];
}
Test code:
int main(int argc,char *argv[])
{
int i;
for(i=0;i<64;i++) {
unsigned long long x=1ULL<<i;
printf("0x%llu -> %d\n",x,fastlog2(x));
}
return 0;
}
The magic 64bit number is an order 6 binary De Brujin sequence.
Multiplying by a power of 2 is equivalent to shifting this number up by a certain number of places.
This means that the top 6 bits of the multiplication result correspond to a different subsequence of 6 digits for each input number. The De Brujin sequence has the property that each subsequence is unique, so we can construct an appropriate lookup table to turn back from subsequence to position of the set bit.
If you use some modern Intel CPU, you can use hardware supported "POPulation CouNT" assembly instruction:
http://en.wikipedia.org/wiki/SSE4#POPCNT_and_LZCNT
for Unix/gcc, you can use macro:
#include <smmintrin.h>
uint64_t x;
int c = _mm_popcnt_u64(x);