0

这是我目前正在处理的家庭作业问题。我们要做的是查看传递的 32 位 int x 并返回将这个值存储在 2s 补码中所需的最少位。

例如：

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

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

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

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

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

4

3 回答 3

1

您可以通过 7 次操作找到 32 位数字的 log_2。查看优秀的Bit Twiddling Hacks

于 2013-02-03T20:26:05.540 回答
0

休斯顿 - 你有问题。

IE

howManyBits(0) = howManyBits(-1) = 1;

因此，您需要至少 2 位为零。（或-1）

于 2013-02-03T19:41:32.977 回答
0

由于这是家庭作业，我不想给你一个直接的答案，但你在 log2 的想法上走在了正确的轨道上。

您可以通过三个操作的组合将其拉出（对于正数）

 1) Shift right 1
 2) Test for 0
 3) Add 1 to a number

希望这足以让你到达那里。由于源数字将是二进制补码，因此您需要先将其转换为正数，以使上述内容生效。

于 2013-02-03T19:49:16.220 回答