c - # 表示数字 x 所需的位数

Question

我目前正在尝试编写一种算法来确定表示数字 x 需要多少位。我的实现将在 c 中。虽然有一些问题，但我几乎只限于按位运算符 {~、&、^、|、+、<<、>>}。此外，我不能使用任何类型的控制流(if、while、for)。我最初的方法是从左到右检查二进制数，并寻找第一个“1”出现的位置。鉴于我的限制，我不确定如何处理这个问题。我正在使用的数字可以被认为是一个无符号整数。所以 00110 只需要 3 位。

我想知道是否有更简单/更清洁的方法来做到这一点，而我错过了它？或者是否有人可以提供一些提示？

基本上，我试图在没有 while 循环的情况下实现它:

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

Answer 1

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

展示了如何在没有控制流的情况下做到这一点。

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++;