【C#】2のべき乗の剰余（モジュロ）をビット演算ANDで高速に計算する方法

剰余（モジュロ）計算といえば通常は % 演算子を使いますが、除数が2のべき乗（2, 4, 8, 16…）である場合は、ビット演算のAND（&)だけで同じ結果を得られます。除算よりもビット演算の方がはるかに軽い処理のため、パフォーマンスが求められる場面でよく使われる定番テクニックです。

仕組み：なぜ「a & (b−1)」で剰余が求まるのか

2のべき乗から1を引いた値は、2進数で見ると下位ビットがすべて1になっています。

• 8 = 1000
• 8 − 1 = 7 = 0111

そこで「被除数 a」と「b − 1」のANDを取ると、a の下位ビットだけが抽出され、その値は a % b の結果と完全に一致します。

例えば a = 9（1001）、b = 8 の場合、1001 & 0111 = 0001 となり、9 ÷ 8 の余り「1」が得られます。

C#での実装例

using System;

class Demo {
    // b が2のべき乗のときのみ正しく動作する
    static uint Mod(uint a, uint b) {
        return a & (b - 1);
    }

    static public void Main() {
        uint a = 9; // 被除数
        uint b = 8; // 除数（2のべき乗）
        Console.WriteLine(a + " % " + b + " = " + Mod(a, b));
    }
}

実行結果

9 % 8 = 1

注意点

• この方法が成立するのは b が2のべき乗の場合のみです。6 など、それ以外の値を指定すると誤った結果になります。
• ここでは符号なし整数（uint）を前提としています。負の値を扱う場合、% 演算子と結果の符号が異なることがあるため注意してください。

応用例

このテクニックは、ハッシュテーブルでバケット位置を求める計算（hash & (tableSize - 1)）のように、高速化が重要な実装で広く利用されています。除算命令をAND一発に置き換えるだけで、処理速度を大きく改善できるケースがあります。