按位与运算符是否等同于取模运算？

Question

我发现以下代码片段，我认为它是将整数转换为二进制的等效形式。 有人能告诉我为什么要使用 &1 而不是 %2 吗？非常感谢。

for (i = 0; i <= nBits; ++i) {
    bits[i] = ((unsigned long) x & 1) ? 1 : 0;
    x = x / 2;
}

- B.T Gutsu

---

那个可怕的条件表达式是怎么回事？它不应该是 (unsigned long) x & 1 != 0) ? (true ? 1 : 0) : (!true ? (x, 0), -0) 吗？ - Kerrek SB

是的，当然可以 :-) 顺便问一下，<= 是正确的吗？ - Kerrek SB

非常感谢你！现在我明白你的意思了;-) - B.T Gutsu

当且仅当n为2的幂次方时，x % n等同于x & (n-1)。我认为人们使用&形式是因为他们认为这是一种微小的优化。 - M.M

@Matt NcNabb：不太对，有符号整数的朝零舍入会引发问题，并且是一些掩码的原因。 - doynax

@doynax 说得好，尽管在有符号整数上执行位运算本质上是不可移植的。 - M.M

Answer 1

无符号整数的表示是由标准指定的：具有 n 个值位的无符号整数表示范围在 [0, 2ⁿ) 中的数字，具有通常的二进制语义。因此，最低有效位是将整数值除以2后的余数。

是否用低级位操作替换可读的数学公式存在争议；这种风格在70年代编译器不太智能时很流行。现在，你可以认为编译器知道除以2可以实现为位移等操作，所以你只需要写出你的意思即可。

- Kerrek SB

---

当处理单个位或进行位运算时，我觉得使用 & 而不是 % 更自然。毕竟，在这种特殊情况下它们只是等价的。 - Jan

我认为这里的问题不在于编译器是否知道 x/2 = x>>1，而在于它是否知道用 & 操作替换 % 操作。答案是否定的，它不知道！ - Pandrei

@Pandrei：编译器通常不允许修改您的源代码！但它可能会为源代码的两个版本生成相同的机器代码。 - Kerrek SB

@KerrekSB 我指的是生成的代码。所以我认为你的回答并没有真正解答我的问题。 - Pandrei

@Jan：嗯，也许吧。如果你真的想进行位运算，当然应该使用位运算。这种情况是否需要它是有争议的；从某种意义上说，它计算的是“按位值表示的整数的数字”，通常使用除法和余数来完成，不需要为二进制特化。但这取决于具体情况。 - Kerrek SB

@Pandrei：请随意发布您自己的答案！ - Kerrek SB

Answer 2

这段代码片段的作用并不是将无符号整数转换为二进制数（它的内部表示已经是二进制的了）。它创建了一个比特数组，其中包含无符号整数位的值。可以将其分散到数组中。

e.g. x=3  =>  bits[2]=0 bits[1]=1 bits[0]=1

为了实现这个目标

1. 它选择数字的最后一位并将其放置在 bits 数组中（使用 &1 操作）。
2. 然后将数字向右移动一个位置（/2 等同于 >>1）。
3. 对所有位重复上述操作

你可以使用 %2 代替 &1，生成的代码应该是相同的。但我想这只是编程风格和偏好的问题。对于大多数程序员来说，&1 要比 %2 更清晰。

- Pandrei

Answer 3

在非常特殊的情况下，它们是等效的。这是一种受Fortran影响的老式风格。

- Jennifer Massey

Answer 4

在您的示例中，%2 和 &1 是相同的。哪个选取可能只是个人喜好的问题。虽然对于数学背景强的人来说，%2 可能更易读，但对于技术背景强的人来说，&1 更易理解。

- MarcelSimon

---

为了保持一致，我认为应该使用 x /= 2 来配合 x % 2；而使用 x >>= 1 来配合 x & 1。我有很强的数学背景，更喜欢 %，所以你可能是对的 :) - M.M

谢谢大家的贡献！ - B.T Gutsu