c++ - 位运算和移位问题

Question

我正在自己测试函数fitBits(int x, int n)，我发现有一个条件不适合这个函数，问题是什么？

/*
* fitsBits - return 1 if x can be represented as an 
*  n-bit, two's complement integer.
*   1 <= n <= 32
*   Examples: fitsBits(5,3) = 0, fitsBits(-4,3) = 1
*   Legal ops: ! ~ & ^ | + << >>
*   Max ops: 15
*   Rating: 2
*/
int fitsBits(int x, int n) {
   int r, c;
   c = 33 + ~n;
   r = !(((x << c)>>c)^x);
   return r;
}

它似乎给出了错误的答案

fitsBits(0x80000000, 0x20);

它给了我 1，但实际上应该是 0...我该如何解决它？谢谢!

Answer 1

fitsBits(0x80000000, 0x20);

此函数返回 1，因为函数的第一个参数是 int，它(在当今的实践中)是一个 32 位有符号整数。有符号 32 位整数可以表示的最大值是 0x7FFFFFFF，它小于您传入的值。因此，您的值会被截断并变成 32 位整数可以表示的 -0x80000000 。因此，您的函数返回 1 (是的，我的第一个参数可以使用 0x20 = 32 位表示)。

如果您希望函数将数字 0x80000000 正确分类为无法使用 32 位表示的内容，则需要更改函数第一个参数的类型。一种选择是使用 unsigned int，但从您的问题定义来看，您似乎需要正确处理负数，因此您剩下的选项是 long long int，可以容纳 -0x8000000000000000 和 0x7FFFFFFFFFFFFFFF 之间的数字。

您将需要进行更多调整:您需要使用 LL 后缀显式指定常量的类型为 long long，并且您现在需要转换通过 64 - c，而不是通过 32 - c:

#include <stdio.h>

int fitsBits(long long x, int n) {
   long long r;
   int c;
   c = 65 + ~n;
   r = !(((x << c)>>c)^x);
   return r;
}

int main() {
    printf("%d\n", fitsBits(0x80000000LL, 0x20));
    return 0;
}

链接到 IDEONE:http://ideone.com/G8I3kZ