1

我一直在研究 Kernighan 和 Ritchie 的“C 编程语言”并阅读了x mod y == x & y-1. 所以，我用铅笔和纸解决了这个问题，效果很好，所以我尝试测试它，问题就在这里：

代码：

#include <stdio.h>

main()
{
  int i, j;

  for(i = 1; i < 10; i++){
    for(j = 1; j < 10; j++)
      printf("%3d",i & j-1);
    printf("\n");
  }
}

给出输出：

  0  1  0  1  0  1  0  1  0
  0  0  2  2  0  0  2  2  0
  0  1  2  3  0  1  2  3  0
  0  0  0  0  4  4  4  4  0
  0  1  0  1  4  5  4  5  0
  0  0  2  2  4  4  6  6  0
  0  1  2  3  4  5  6  7  0
  0  0  0  0  0  0  0  0  8
  0  1  0  1  0  1  0  1  8

和

#include <stdio.h>

main()
{
  int i, j;

  for(i = 1; i < 10; i++){
    for(j = 1; j < 10; j++)
      printf("%3d",i % j);
    printf("\n");
  }
}

给出输出：

  0  1  1  1  1  1  1  1  1
  0  0  2  2  2  2  2  2  2
  0  1  0  3  3  3  3  3  3
  0  0  1  0  4  4  4  4  4
  0  1  2  1  0  5  5  5  5
  0  0  0  2  1  0  6  6  6
  0  1  1  3  2  1  0  7  7
  0  0  2  0  3  2  1  0  8
  0  1  0  1  4  3  2  1  0

请注意，唯一的变化%是&. 任何输入将不胜感激

4

1 回答 1

6

方程

x mod y == x & y-1

仅对y2 的幂是正确的。

如果y = 2^k， 的二进制表示y是一个 1 位后跟k0 位（并且前面有多个 0 位，具体取决于类型的宽度），并且 的表示y-1是k1 位（前面有 0）。

那么如果你写x = q*y + rwith 0 <= r < y，二进制表示r最多需要位k，而 的最后一位都是 0，所以模的余数由 的最低有效位组成，这些位是通过按位和 with 获得的。kq*yxykxy-1

对于奇数y > 1，y-1是偶数，所以x & y-1总是偶数，因此(y+1) % y == 1 != (y+1) & (y-1)。即使y不是 2 的幂，也将 1 替换为对应于 in 的最低设置位的 2 的y幂y+1。

于 2012-10-28T20:45:14.493 回答