按位运算：FitsBits

Question

我在写FitsBits的时候遇到了一些问题，google了一下，找到了适合测试程序的解决方案，但是我想不通是什么意思。

问题描述：

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

正确的解决方案是：

int fitsBits(int x, int n)
{   
int move;  
move = 32 +(~n+1);
return !(x^((x<<move)>>move)); 
}

但是我不知道

!( x ^ ( ( x<< 移动 ) >> 移动 ) )

是什么意思。

我真的需要一些help.Thx！

Answer 1

此问题与 Bitwise operations and shifts 重复，用户要求理解相同的代码。不幸的是我没有标记它的声誉。

重申一下Code-Apprentice's answer and AnT's，根据您找到的解决方案进行一些修改，并根据我自己的解释进行更多解释

move = 32 +(~n+1);

这其实就是32（本题中n的最大值，整数大小）与n的差值。

了解为什么要研究二进制补码有符号整数。在这种格式中，您可以将无符号整数（例如在原始示例中的 5 (0101)）转换为 -5，方法是反转位并加一

~5 + 1 = -5

或

~(0101) + 1 = 1011

注意 1011 不能放入 3 位并且仍然是负数（2s 补码中的负数必须以 1 开头）

所以

move = 32 +(~n+1);

实际上是

move = 32 - n;

最后一行实际上是一行中的几个想法

!(x^((x<<move)>>move));

所以让我们分解它。

invert the truthiness of 
    (x xor a number) 
        where the number is x first shifted left then right amount move
            and move is the difference between n and 32.

让我们再次使用 5 和 3 的例子。我们知道move应该是32 -3，所以move是29。

但为什么左右移动相同的量？通常，当您看到有人在代码中执行此操作时，他们正试图 'zero out' 一个数字。在这种情况下，作者并没有这样做，而是符号扩展。往下看

例如：

given 0000 0000 0000 0000 0000 0000 0000 0101 = 5
5 << 29 = 1010 0000 0000 0000 0000 0000 0000 0000 = -1610612736
-1610612736 >> 29 = 1111 1111 1111 1111 1111 1111 1111 1101 = -3

作者正在使用 rshift 的实现级别怪癖，如果数字以带符号开始，它会保留其符号，并在移位时用符号填充数字的其余部分。

请注意，由于符号填充 (5 >> 29) << 29 不会产生相同的数字，因为当我们将 5 移到 32 位有符号数的末尾时，它从 1 开始，因此自己签名。

下一行就简单多了

(x ^ number)

如果 x == 数字，

将为 0，因为 0 xor 1 = 1，并且 1 xor 1 = 0，并且 0 xor 0 = 0。所以按照这个逻辑，当我们反转 x 的真实性时，我们是检查是否

x == (sign shifted x)

如果 5 是，比方说，8 而不是 (1000)，我们将简单地丢失最后一位数字 (1)，然后我们会发现

!(8 ^ 0) == false.

如果我们选择使用一个实际有效的数字（比如 3），因为 3 = 011，并且将 3 右移 29 将导致第一位为 0，我们将在移回时保留 3 的值来回，所以我们会发现

!(3 ^ 3) == true;

总结一下这个函数真的只是做以下事情

given int x and int n,
check if x == (x shifted left then sign shifted right by (size of int in bits - n) )

按位运算：FitsBits

Bitwise operation : FitsBits

bitwise-operators