C - 简单模数表的麻烦,它不是那么简单

Question

我一直在通过Kernighan和Ritchie"The C Programming Language"进行处理并阅读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

请注意,唯一的变化就是%变成了&.任何输入都将非常感激

Answer 1

等式

x mod y == x & y-1

仅对y 2的幂是正确的.

如果y = 2^k,二进制表示y是一个1位后跟k0位(并且前面有一些0位,具体取决于类型的宽度),并且表示y-1为k1位(前面带有0).

然后,如果你写的x = q*y + r与0 <= r < y,的二进制表示r需要至多k位,最后k的位q*y都是0,所以剩余x模y由至少显著的k位x,这是由按位与获得y-1.

因为奇数y > 1,y-1偶数,所以x & y-1总是均匀,因此(y+1) % y == 1 != (y+1) & (y-1).即使y不是2的幂,也要用2的幂替换1,对应于yin 的最低设置位y+1.