使用按位运算查看 int x 是否适合 n 位的 C 函数

Question

/* 
 * 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) {
  /* mask the sign bit against ~x and vice versa to get highest bit in x. Shift by n-1, and not. */
  int mask = x >> 31;

  return !(((~x & mask) + (x & ~mask)) >> (n + ~0));

}

我有这个功能，但我不明白为什么我们要用那个面具遮住 ~x。我的理解是 x >> 31 会将最后一位（符号位）带到最正确的位置。为什么我们需要那个位置的符号位。为什么我们必须添加第二个掩码的结果，为什么我们要右移 n - 1 个空格？我迷路了，我不知道从哪里开始了解这个功能。请帮助我开始。

Answer 1

int fitsBits(int x, int n) {
  int mask = x >> 31;

  return !(((~x & mask) + (x & ~mask)) >> (n + ~0));

}

mask就是你说的符号位

if mask is 0x01
    (~x & mask) last bit of x, but flipped `0 <-> 1`
    (x & ~mask) everything except the last bit
if mask is 0x00
    (~x & mask) is always 0x00
    (x & ~mask) is always x

所以我们有

if positive (~x & mask) + (x & ~mask) evaluates to just x
if negative (~x & mask) + (x & ~mask) evaluates to x with the last (least) bit switched

(n + ~0) is equivalent to (n-1), at least for n >= 0

当然还有！最后使非零值变为 0，零值变为 1

之所以将最后一位切换为负数，是因为在二进制补码中，负数允许大于正数

Answer 2

更新：

算术和逻辑移位运算的左移操作相同，因为值的 sign-ness 不是用最低有效位表示，而是用最高有效位表示。变得复杂的地方是向右移位操作。

这个函数的一个问题是它假定右移操作是一个算术移位，其中 sign-ness 的值是受保护的。算术移位是通过用与先前存在的值相同的值填充最高有效位的槽来进行的。这意味着，如果您将表示负值（负符号整数）的二进制数向右移动，根据负整数表示的规则，右移操作在数学上将是一致的，因此结果值为负并除以二。还有一种叫做逻辑移位的东西，其中从前一个值向右移位的最高有效位将始终为零，这与 left-shift 中发生的情况相同。在这种情况下，右移操作将与整数表示不一致。

以上函数假定移位操作始终是一种算术移位操作。但是，如果您查看以下来源

Are the shift operators (<<, >>) arithmetic or logical in C?

它说右移操作是 implementation-defined 这意味着不能保证右移操作永远是逻辑或算术移位。它还指出右移是 "most of the time" 作为算术移位实现的，但不必那样做。

例如，Java有两个左移运算符>>>和>>。前者强制逻辑移位，后者强制算术移位

int mask = x >> 31;

右移 31 的主要思想是能够区分负整数和正整数。根据符号扩展规则，如果一个负数向右移动任意大小，则在整个右移过程中重复最高有效位的值以保持数字的符号。

return !(((~x & mask) + (x & ~mask)) >> (n + ~0));

这里有点复杂，分一下吧，

//Either x or y has to be zero since mask either will be all zeroes or ones
a = (~x & mask)
b = (x & ~mask) 

//When added together, since x or y will always be zero, number to be used is returned
//Hence addition is used to simulate logical OR operation.
c = (a OR b) >> (n - 1)

//Any remaining non-zero bit means N wasn't sufficient 
result = !c

如上所示，整个 return 语句可以分为上面所示的逻辑步骤。现在让我们通过 straight-forward 方式重写代码来评估它们可能意味着什么，

int fitsBits(int x, int n) {
   int res = -1;
   if(x >= 0){
       res = (x >> (n - 1));
   }
   else if (x < 0){
       res = (~x >> (n - 1));
   }
   return !res;
}

n-1 移位用于正数。由于数的最高位仅用于检测数字的符号，因此在未使用最高位的情况下将正数移动 n 会给出错误的结果。基本上我们需要一个虚拟位来显示一个数字是正数还是负数，通过移动 n -1，我们确保我们有足够的空间容纳那个位。下面是一个示例

4 is 00100. Can be represented using n=3 bits? Let's look at it.
Shift by 3, result is !00000 = 1, this true for unsigned int but not for signed int
Shift by 2, result is !00001 = 0, more correct representation.

如何计算负数？

2 的补码规则用于使用二进制计数系统表示负整数和正整数。这是一种相互转换编号系统的方法。还有另一个称为 1 的补码的系统，其中正负之间的差异是通过反转所有位来确定的。但是在这种情况下，存在称为负零和正零的条件。为了避免这种情况，在翻转所有位后添加 1 的地方使用 2 的补码。

在 fitsBits 函数的情况下，如果数字为负数，它足以反转所有位，这是因为它将给出值 -(x) - 1，其中 x 为负数。比方说，如果你有 -3，~ 操作会给你 -(-3) - 1 = 2.

根据补码规则，-3用公式-(x)-1取反后必须为2。如果~运算不满足-(x) - 1使用给定的位数，这意味着位槽数不足。

使用按位运算查看 int x 是否适合 n 位的 C 函数

C function that uses bitwise operations to see if an int x fits in n bits

c

bit-manipulation

bitwise-operators