(x & 3)이 (x mod 4)와 동일한 이유는 무엇입니까?

Question

저자가 % 연산자 대신 비트를 & 연산자로 사용하는 것으로 보이는 예제 소스 코드를 발견했습니다. 그러나 x & 4 시도했을 때 x % 5 같은 값을 생성하지 않습니다. 이 단지 x >= 0에 대한 진실에 따라 수 있음을 또한

x AND (2^n - 1) 

참고 :

x MOD 2^n 

가 동일합니다 :

Answer 1

에만 일반적으로 2

의 힘을 작동 x < 0에 대한 MOD의 정의.

---

는 이유이 작품을 이해 MOD 정말 무엇을 생각합니다 - 그것은 정수 나누기를 수행 한 후 바로 나머지입니다. 2^n에 의한 나눗셈의 경우, 우리는 효과적으로 2 진 값을 n 비트 씩 시프트하고, 시프트 아웃 된 임의의 하위 비트를 폐기한다. 우리로 나누면 8 비트 이진수

a b c d e f g h 

4 = 2 우리는 2 비트 씩 우측 시프트^2

나머지 ( g h)의 결과로서 폐기 된

0 0 a b c d e f 

정수부.

우리가 다음 우리가 0 0 0 0 0 0 1 1의 마스크 적용하여 비트를 g h를 추출 할 수 나머지를 알고 싶어 경우 :이 일반적인 경우에 단지 2 값 3을 가지고 있는지

a b c d e f g h 
AND 0 0 0 0 0 0 1 1 
    = 0 0 0 0 0 0 g h 

참고^n - 1

실제 숫자를 사용해 보겠습니다.

42/4 (decimal) 
= 0 0 1 0 1 0 1 0 >> 2 
= 0 0 0 0 1 0 1 0 
= 10 (decimal) 

    42 MOD 4 (decimal) 
= 0 0 1 0 1 0 1 0 AND 0 0 0 0 0 0 1 1 
= 0 0 0 0 0 0 1 0 
= 2 (decimal) 

그래서 4분의 42 = 10 나머지 2 :

42 = 0 0 1 0 1 0 1 0 

우리가이 비트에 의해 오른쪽 시프트 몫을 얻으려면 우리가 4분의 42를 계산하고 몫과 나머지를 모두 얻을한다고 가정

Answer 2

답변은 매우 간단하며 이진으로 생각하십시오.

0000 = 0 AND 11 = 0000 = 0 
0001 = 1 AND 11 = 0001 = 1 
0010 = 2 AND 11 = 0010 = 2 
0011 = 3 AND 11 = 0011 = 3 
0100 = 4 AND 11 = 0000 = 0 
0101 = 5 AND 11 = 0001 = 1 
0110 = 6 AND 11 = 0010 = 2 
0111 = 7 AND 11 = 0011 = 3 

... 등등.

알림과 동일한 결과 (%는 나머지, 공식적으로는 모듈러스가 아닙니다)입니다. 2의 제곱근에서만 작동하며 0과 양수에 대해서만 사용됩니다.