c - 寻找最少的位来存储 int 的 2 补码

Question

这是我目前正在做的家庭作业。我们要做的就是查看传递的 32 位 int x 并返回以 2 补码形式存储该值所需的最少位。

例如:

howManyBits(0) = 1;
howManyBits(-1) = 1;
howManyBits(7) = 4;
howManyBits(-10) = 5;

问题在于我只能使用按位运算符来找到它，我不能有大于一个字节的常量，而且我的操作总数不能超过 90 次。目前，我可以从最高有效位开始一直涂抹 1，然后对其中的每个 1 进行计数。然而，由于它是一个 32 位 int，并且每次检查是否有位翻转时，我都必须将 int 向右移动 1 以上，因此对位进行计数的过程本身需要 90 次操作，并且由于位涂抹花了 20 个，我远远超过了最大操作数。

此外，我不会在解决方案中大声使用条件或循环。

我知道如果我能找出一个可以解决这个问题的 log_2 算法，但我也无法仅用按位运算符来解决这个问题。

我想要的只是一个提示/解释一个可以用更少的操作完成的过程，而不是一个实际的代码解决方案。谢谢!

Answer 1

需要 7 次运算才能找到 32 位数字的 log_2。查看优秀Bit Twiddling Hacks