# of bits needed to represent a number x

Question

I am currently trying to write an algorithm that determines how many bits are necessary to represent a number x. My implementation will be in c. There are a few catches though, I am restricted to pretty much just the bitwise operators {~, &, ^, |, +, <<, >>}. Also, I cannot use any type of control flow (if, while, for). My original approach was to examine the number in binary from left to right, and look for where there is an occurrence of the first '1'. I am not sure how to approach this given the restrictions I have. The number I am working with can be considered an unsigned integer. So 00110 would require only 3 bits.

I am wondering if there is a much easier/cleaner way to do this and I am missing it? Or if someone can give a few hints?

Basically, I was trying to implement this without the while loop:

 int result = 0;
  while (x >>= 1) {
    result += 1;
  }
  return result;

Answer 1

http://www-graphics.stanford.edu/~seander/bithacks.html#IntegerLog

Shows how to do it without control flow.

unsigned int v;          // 32-bit value to find the log2 of 
register unsigned int r; // result of log2(v) will go here
register unsigned int shift;

r =     (v > 0xFFFF) << 4; v >>= r;
shift = (v > 0xFF  ) << 3; v >>= shift; r |= shift;
shift = (v > 0xF   ) << 2; v >>= shift; r |= shift;
shift = (v > 0x3   ) << 1; v >>= shift; r |= shift;
                                        r |= (v >> 1);
r++;