按位运算和移位操作

Question

我有些难以理解这段代码的工作原理和原因。我的合作者已经完成了这部分，但我无法联系到他，以便找出这个代码如何以及为什么能够工作。我尝试了几种不同的方法来理解它，但任何帮助都将不胜感激。这段代码使用2的补码和32位表示。

/* 
 * 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;
}

- Scalahansolo

---

这是一种高深的巫术。你不需要真正理解它，只需将其作为来自高层的智慧接受。提示：如果位置n-1左侧的所有位具有与位置n-1处的位相同的值，则它适合。 - David Schwartz

了解每个运算符的作用（并理解二进制补码），然后推断各种输入值会发生什么。要轻松阅读上述内容需要大量练习。 - Bernhard Barker

不错的拼写！真的很神奇。 - philx_x

Answer 1

c = 33 + ~n;

这个计算是用于确定在使用n个低位比特后剩余了多少高位比特。

((x << c)>>c

这将使用与 x 的符号位相同的值来填充高位。

!(blah ^ x)

这相当于

blah == x

- Code-Apprentice

---

只是出于兴趣，我想知道为什么他们没有使用(x & ~(1 << c))而是使用了((x >> c) << c)？这将消除一个中间依赖项，可能会在乱序流水线处理器上节省一个或两个周期。 - SecurityMatt

@SecurityMatt 我相信有几种方法可以实现同样的事情。 - Code-Apprentice

@SecurityMatt：如果输入为负数，它将无法正常工作。 (x << c) >> c 的目的不是清零高阶位（正如此答案错误地说明的那样），而是符号填充它们。对于负值，填充物是1，而不是0。这正是使此代码适用于负值的原因。 - AnT stands with Russia

@ovgolovin：只要实现细节在我的答案中有列举，它就可以处理负值。一般来说，这不是一个便携式的实现，因此它不能处理任何值。 - AnT stands with Russia

@Seb：是的，但不仅如此。这个实现还依赖于一些正值在它们的高位比特移动到符号位位置时变为负数。这对于使这段代码拒绝例如(5, 3)的输入至关重要。当然，从正式上讲，这也是未定义行为。 - AnT stands with Russia

Answer 2

在2的补码平台上，-n 等同于 ~n + 1。因此，对于这个原因，在这种平台上，c = 33 + ~n 实际上等同于 c = 32 - n。这里的 c 表示如果 n 个低位被占用，则在32位 int值中保留了多少高阶位。

请注意，这段代码中存在两个与平台相关的部分：2的补码平台，32位的int类型。

然后 ((x << c) >> c 旨在符号填充这些 c 高阶位。符号填充意味着那些在位 n - 1 位置上为 0 的 x 值，这些高阶位必须被清零。但对于那些在位 n - 1 位置上为 1 的 x 值，这些高阶位必须被填充为 1。这对于使代码在 x 为负数时正常工作非常重要。

这引入了另外两个平台相关的部分：<< 运算符在移动负数值或将 1 移动到符号位时的行为良好（正式上这是未定义的行为），>> 运算符在移动负数值时进行符号扩展（正式上这是实现定义的）。

其余部分，正如上文所述，只是与原始值x的比较：!(a ^ b) 等同于 a == b。如果上述变换没有破坏原始值 x，那么 x 的确适合于2的补码表示中的n 个低位。

- AnT stands with Russia

Answer 3

对带符号整数使用按位补码（一元~）运算符具有实现定义和未定义的方面。换句话说，即使只考虑二进制补码实现，这段代码也不具备可移植性。

---

需要注意的是，即使在C语言中使用二进制补码表示法也可能有突陷表示法。6.2.6.2p2甚至明确说明了这一点:

如果符号位为1，则value应以以下方式修改:

-- 对应的带有符号位0的值被否定(符号和大小);

-- 符号位的值为 -(2 M ) (二进制补码);

-- 符号位的值为 -(2 M - 1) (补数).

实现定义哪个适用于这些情况，是否将符号位为1且所有值位为0（对于前两种情况）或符号位和所有值位为1（对于补数）视为陷阱表示法或正常值也是如此。

强调是我的。 使用陷阱表示法是未定义行为。

在默认模式下，有一些实际的实现将该值保留为陷阱表示。我通常引用的一个著名的实现是Unisys Clearpath Dordado on OS2200 (go to 2-29)。请注意该文档的日期；这样的实现并不一定古老（这也是我引用此文档的原因）。

---

根据6.2.6.2p4，将负值向左移动是未定义的行为。我没有对实际存在的行为进行过多的研究，但我合理地期望可能会有一些实现进行符号扩展，也可能有一些实现不这样做。这也是形成上述提到的“陷阱表示”的一种方式，其性质是未定义的，因此不可取。从理论上讲（或者在遥远或不那么遥远的将来），您可能还会面临“对应于计算异常的信号”（这是类似于SIGSEGV的C标准类别，对应于诸如“除以零”之类的事情）或其他不稳定和/或不可取的行为...

---

总之，这个问题中的代码能够工作的唯一原因是你实现所做的决策恰好对齐。如果你使用我列出的实现方法，你可能会发现这段代码对于某些值并没有按照预期工作。

如评论中所描述的那样，这种重型巫术并不是必需的，也不是我认为看起来最优的解决方案。如果你想要一个不依赖魔法（例如，可移植的）来解决这个问题的方案，请考虑使用这个（实际上，这段代码至少可以处理1 <= n <= 64）：

#include <stdint.h>

int fits_bits(intmax_t x, unsigned int n) {
    uintmax_t min = 1ULL << (n - 1),
              max = min - 1;
    return (x < 0) * min + x <= max;
}

- autistic

---

这个问题说：“这段代码使用了二进制补码和32位表示法。”所以你的异议不相关。在二进制补码中，~可能不会产生陷阱表示（6.2.6.2/1脚注53）。 - M.M

如果您继续阅读，可能会注意到我提到了将负值左移的UB（未定义行为）...您是在说这与此无关吗？ - autistic

@MattMcNabb即便如此，这个回答提出的问题确实相关，是否仍值得被点踩？ - autistic

@MattMcNabb，说得好。实际上我已经很久以前就删除了关于16位的部分，而你支持陷阱表示法的论点仅仅是信息性的，而我的则是规范性的。无论如何，我会把这个留在这里，即使只是作为证据，证明一些SO用户的固执。 - autistic

在二进制补码中，对于范围在[1, 32]之间的n，33 + ~n不能生成陷阱表示是规范的。 - M.M