정수 n을 2의 거듭제곱으로 나눈 나머지를 효율적으로 구하는 방법

나머지를 구할때 %로 구하면 되는데.. 효율적으로 구한다는게 도대체 무슨말인가?

 

%연산은 계산 비용이 높아서 비효율적으로 알려져있다.

 

n = 98

print(n % 2) #0
print(n % 4) #2
print(n % 8) #2
print(n % 16) #2
print(n % 32) #2

 

계산비용을 줄이고 싶다면 % 연산자를 사용하지 않고 나머지를 구해야한다.

 

예를 들어 4로 나눈 나머지를 어떻게 구할 수 있을까?

 

컴퓨터는 모든 수를 2진수로 인식하기 때문에.. 가장 쉬운 접근은 정수 n을 2진수로 나타내보는 것이다.

 

 

위 그림을 보면 어떤 수를 4로 나눈 나머지는 0,1,2,3중 하나인데... n을 2진수로 나타냈을때 4로 나눈 나머지는...

 

n의 2진수 표현에서 오른쪽 끝의 2비트만 가져오는 것임을 알 수 있다.

 

비트연산자 중에서 & 연산자는 1 & 1  = 1이고 1 & 0 = 0이다.

 

1과 & 연산을 하면 해당 비트를 그대로 가져온다는 특징이 있다.

 

10진수 3은 2진수로 나타내면 11이다.

 

그러므로 10진수 n을 3과 & 연산을 하면 오른쪽 마지막 2비트를 그대로 가져온다.

 

그리고 그것이 n을 4로 나눈 나머지가 된다.

 

n = 98

print(n & 3) # 2

 

일반적으로 확장할 수 있다.

 

2로 나눈 나머지는 어떻게 구할 수 있을까? 

 

0 아니면 1이다. 해당 정수 n의 마지막 1비트만 가져오면 된다. 

 

그러므로 n & 1로 구할 수 있다.

 

8로 나눈 나머지는?

 

0,1,2,3,4,5,6,7이다. 해당 정수 n의 마지막 3비트만 가져오면 된다.

 

그래서 n & 7로 구할 수 있다.

 

일반적으로 정수 N을 $2^{n}$으로 나눈 나머지는... N과 $2^{n}-1$의 &연산으로 구할 수 있다.

 

 

 

Find the remainder when N is divided by 4 using Bitwise AND operator - GeeksforGeeks

Find the remainder when N is divided by 4 using Bitwise AND operator - GeeksforGeeks