位运算和移位问题

Question

我正在自己测试函数 fitsBits(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

有符号类型未定义导致溢出的左移。因此，编译器可能会将 (x<<c)>>c 优化为简单的 x，并且整个函数会缩减为 return 1;.

可能您想使用无符号类型。

代码中未定义行为的第二个原因是 c 可能大于或等于 int 的宽度。超过整数类型宽度的移位是未定义的行为。

Answer 2

r = (((x << c)>>c)^x); //This will give you 0, meaning r = 0;

或

r = !((x << c)>>c);

你的函数可以简化为

int fitsBits(int x) {

    int r, c; 
    c = 33; 
    r = (((x << c)>>c)^x);

    return r;
}

请注意，当出现 NOT(!) 时，您要求的是 r

的反义词

Answer 3

fitsBits(0x80000000, 0x20);

这个函数 returns 1，因为你的函数的第一个参数是 int，这是（现在实际上）一个 32 位有符号整数。带符号的 32 位整数可以表示的最大值是 0x7FFFFFFF，它小于您传入的值。因此，您的值被截断并变为 -0x80000000，这是 32 位整数可以表示的值。因此你的函数 returns 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;
}

Link 至 IDEONE：http://ideone.com/G8I3kZ

位运算和移位问题

Bitwise operations and shifts problems

c

c++

bit