需要表示数字x所需的位数

Question

我目前正在尝试编写一个算法，确定表示数字x所需的位数。 我的实现将使用c语言。 然而有一些限制，我基本上只能使用位运算符{〜，＆，^，|，+，<<，>>}。此外，我不能使用任何类型的控制流（if，while，for）。 我的原始方法是从左到右检查二进制中的数字，并查找第一个“1”的出现位置。考虑到我的限制，我不确定该如何实现这一点。 我正在使用被视为无符号整数的数字。因此，00110只需要3位。 我想知道是否有更轻松/更简洁的方法来做到这一点并且我遗漏了它？ 或者，如果有人可以给出一些提示？ 基本上，我正在尝试在不使用while循环的情况下实现这个功能：

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

- Chris Dargis

---

这个数字是整数还是浮点数？最大值和最小值是多少？有符号还是无符号？ - Adam Liss

@AbhijeetRastogi：是的，这是我在计算机架构课程中要解决的最后一个“难题”之一。我有各种各样需要位操作的问题，目前我已经完成了大约80％的进度，但这是我真的无法开始解决的最后一个问题。 - Chris Dargis

@AdamLiss：该数字被解释为无符号整数。 - Chris Dargis

在你的例子中，结果不应该从1开始吗？传入x = 00110将返回2，因为在循环第三次时，x将等于000000，因此不会增加结果。 - Tyler Petrochko

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

- Keith Nicholas

---

请注意，他写道“我不能使用任何类型的控制流”。 - shadyabhi

这篇帖子说没有控制流，我认为这意味着没有 while 循环。 - TJD

">"是一种条件控制流。谢谢，但不幸的是，这个解决方案不起作用。 - Chris Dargis

展开循环意味着它不再是一个循环，即没有分支。 :) - Keith Nicholas

@AntoineMathys 这不是汇编语言，但许多汇编器可以进行比较，然后获取比较的值而无需分支。请注意，在这种情况下，它只需要标志状态继续，它不会根据结果进行分支（尽管编译器可能会决定分支，如果它认为更有效）。但无论如何，问题是关于C语言的，他会接受它，因为当他查找<运算符时，他会发现它不是条件语句，也不是控制流，因此是一个可接受的答案。 - Keith Nicholas

Answer 2

请尝试以下方法：

// http://www.cs.northwestern.edu/~wms128/bits.c
int check_bits_fit_in_2s_complement(signed int x, unsigned int n) {
  int mask = x >> 31;

  return !(((~x & mask) + (x & ~mask))>> (n + ~0));
}

- oon

Answer 3

被接受的答案实际上是错误的：例如，它对于32..63输出5（而不是6），对于16..31输出4（而不是5）。这就像取以2为底的对数并向下舍入。

正确的解决方案如下：

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

请注意 r++。

- Unai Vivi

Answer 4

嗯，我认为他需要一个首位计数器而不是末位计数器。由于该算法涉及32位整数，因此结果需要进行修复。

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);
return 32-r;

- NalaGinrut