How to find n where k = 2^n

Question

If I know an integer k = 2^n, how can I efficiently find n? In other words, if I know a single bit in a integer is set, how can I get the location of the bit?

An idea is to find the Hamming Weight of k-1 but are there any other simpler ways I'm not thinking about?

Count the number of single-place right shifts before the value is 0. There may be other techniques too — check out [Bit Twiddling Hacks](http://graphics.stanford.edu/~seander/bithacks.html). — Jonathan Leffler, Mar 21 '15 at 06:49
I upvoted this because although the "duplicate" gives the answer you probably need, knowing in advance that it is a power of two might have changed the answer; not a bad question therefore imho. Also note that the answers given somehow are all different from what I use [...] (as hard-core coder): https://github.com/CarloWood/ai-utils/blob/master/log2.h — Carlo Wood, Mar 15 '19 at 14:33

score 1 · Answer 1 · edited May 23 '17 at 12:22

Bit Twiddling Hacks have a lot of amazing (and obscure, performance oriented) bit hacks. The best one for your use seems using multiply and lookup.

unsigned int v;  // find the number of trailing zeros in 32-bit v 
int r;           // result goes here
static const int MultiplyDeBruijnBitPosition[32] = 
{
  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];

This page provides a detailed analysis of the problem with a focus on chess programming.

Answer copied from here. PS: Didn't know how to give credit to the author on that question, and so wrote it like this.

How to find n where k = 2^n

1 Answers1