[解決済み] ビット単位で、モジュラス演算子の代わりに使用

質問

例えば2の累乗のモジュロはこのように表現できることが分かっています。

x % 2 inpower n == x & (2 inpower n - 1).

例

x % 2 == x & 1
x % 4 == x & 3
x % 8 == x & 7 

一般的な2のべき乗でない数値は？

としましょう。

x % 7==?

どのように解決するのですか？

まず第一に、実は次のように言うのは正確ではありません。

x % 2 == x & 1

簡単な反例です。 x = -1 . Javaを含む多くの言語では -1 % 2 == -1 . つまり % は必ずしも伝統的な数学のモジュロの定義ではありません。たとえば、Java では、これを "remainder operator" と呼びます。

ビット単位の最適化に関して、ビット単位の演算で "簡単に"できるのは 2 の累乗のみです。一般に、基数のモジュロ累乗のみが b の累乗のみがビット演算で可能です。 b で表現することができます。

10進数では、例えば、非負の場合 N , N mod 10^k は単に最下位の k の数字を取るだけです。

参考文献

• JLS 15.17.3 余剰演算子 %.
• Wikipedia/Modulo オペレーション