Finding the exponent of n = 2**x using bitwise operations [logarithm in base 2 of n]

Question

Is there a straightforward way to extracting the exponent from a power of 2 using bitwise operations only?

EDIT: Although the question was originally about bitwise operations, the thread is a good read also if you are wondering "What's the fastest way to find X given Y = 2X in Python?"**

I am currently trying to optimize a routine (Rabin-Miller primality test) that reduces an even number N in the forms 2**s * d. I can get the 2**s part by:

two_power_s = N & -N

but I can't find a way to extract just "s" with a bitwise operation. Workarounds I am currently testing without too much satisfaction (they are all pretty much slow) are:

• using the logarithm function
• manipulating the binary representation of 2**s (i.e. counting the trailing zeroes)
• looping on a division by 2 until the result is 1

I am using python, but the answer to this question should be language agnostic, I suppose.

Answer 1

"language agnostic" and worrying about performance are pretty much incompatible concepts.

Most modern processors have a CLZ instruction, "count leading zeros". In GCC you can get to it with __builtin_clz(x) (which also produces reasonable, if not the fastest, code for targets that lack clz). Note that this CLZ is undefined for zero, so you'll need an extra branch to catch that case if it matters in your application.

In CELT ( http://celt-codec.org ) the branchless CLZ we use for compliers lacking a CLZ was written by Timothy B. Terriberry:

int ilog(uint32 _v){
  int ret;
  int m;
  ret=!!_v;
  m=!!(_v&0xFFFF0000)<<4;
  _v>>=m;
  ret|=m;
  m=!!(_v&0xFF00)<<3;
  _v>>=m;
  ret|=m;
  m=!!(_v&0xF0)<<2;
  _v>>=m;
  ret|=m;
  m=!!(_v&0xC)<<1;
  _v>>=m;
  ret|=m;
  ret+=!!(_v&0x2);
  return ret;
}

(The comments indicate that this was found to be faster than a branching version and a lookup table based version)

But if performance is that critical you probably shouldn't be implementing this part of your code in python.