1

私はカーニハンとリッチーの「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

2の累乗に対してのみ正しいです。y

の場合y = 2^k、のバイナリ表現yは1ビットの後にk0ビットが続き（タイプの幅に応じて0ビットの数が前に付きます）、の表現y-1はk1ビット（0が前に付きます）です。

次に、を使用して書き込む場合、必要性のバイナリ表現は最大でx = q*y + rビット0 <= r < yであり、の最後のビットはすべて0であるため、モジュロの残りの部分は、ビット単位およびで取得されるの最下位ビットで構成されます。rkkq*yxykxy-1

奇数y > 1の場合、y-1は偶数であり、x & y-1常に偶数であるため、(y+1) % y == 1 != (y+1) & (y-1)。2の累乗ではない場合でも、1をinyの最下位セットビットに対応する2の累乗に置き換えます。yy+1

于 2012-10-28T20:45:14.493 に答える