C#에서 2의 거듭제곱으로 나머지(모듈로) 연산 빠르게 계산하는 방법

나누는 수가 2의 거듭제곱일 때는 비트 AND 연산자 &를 활용하면 일반적인 나머지 연산자 %보다 훨씬 빠르게 모듈로(나머지) 값을 구할 수 있습니다.

핵심 원리

나누는 수가 2의 n제곱이라면, 피제수에서 하위 n비트만 남기면 그 값이 곧 나머지가 됩니다. 이를 수식으로 표현하면 다음과 같습니다.

a % b == a & (b - 1)  // 단, b는 반드시 2의 거듭제곱이어야 함

예를 들어 8은 2³이므로, 어떤 수를 8로 나눈 나머지는 해당 수와 7(즉 8−1)을 비트 AND 연산한 결과와 동일합니다. 이 방법은 나눗셈 명령 대신 단순한 비트 연산만 수행하므로 성능이 중요한 코드에서 유용하게 사용됩니다.

예제 코드

아래 예제에서 a는 피제수(dividend), b는 나누는 수(divisor)입니다.

using System;
class Demo {
   static uint display(uint a, uint b) {
      return ( a & (b - 1) );
   }
   static public void Main() {
      uint a = 9;
      uint b = 8;
      Console.WriteLine(a + " modulus " + b + " = " + display(a, b));
   }
}

출력 결과

9 modulus 8 = 1

동작 과정 살펴보기

위 예제에서 9는 이진수로 1001, 8−1인 7은 0111입니다. 두 값을 비트 AND하면 하위 3비트인 001, 즉 1이 남습니다. 실제로 9 ÷ 8의 나머지도 1이므로 두 결과가 일치하는 것을 확인할 수 있습니다.

주의 사항

이 기법은 b가 정확히 2의 거듭제곱(1, 2, 4, 8, 16, …)일 때만 올바른 결과를 보장합니다. 그 외의 값에는 반드시 표준 나머지 연산자 %를 사용해야 합니다.