비트 연산으로 산술연산 빠르게 처리하기

<< n 이 2의 n제곱이고
>> n 은 2를 n번 나눈 것이고
위의 것들은 익히 잘 알려져 있고 꽤 쓰이는 듯 하다.

다음으로 2의 n제곱 단위의 수를 나눈 나머지 연산의 경우도
앤드 연산으로 가능하다.
i % 2  =>  i & 1
i % 4  =>  i & 3
i % 8  =>  i & 7
i % 16  =>  i & 15
i % 32  =>  i & 31
....
i % 2의 n제곱  =>  i & (2의 n제곱 - 1)
나머지 연산보다는 비트 연산이 비할바 없이 빠르다.
참고로 릴리즈 실행 화일을 올리디버거 사용하여 어셈블리 코드를 뜯어보니
역시나 컴파일러가 저 경우 앤드 연산으로 알아서 최적화 코드를 생성함을 알 수 있었다.

다음으로 xor 연산으로 특정한 경우 뺄셈처리가 가능하다.
가령 32개의 요소가 있는 경우 0 ~ 31까지 인덱스를 역순으로 처리하고자 할 때
31 - i
보통 위와 같이 사용가능한데 이것은 아래처럼 가능하다.
31 ^ i 
이 경우  물론 31처럼 값이 (2의 n제곱 - 1)이어야 된다.
(2의 n제곱 - 1) - i  => (2의 n제곱 - 1) ^ i

아무튼간에 31 - i 이  31 ^ i 와 같다니 수의 세계가 뭔가 오묘하기도 하다.
평상시 xor 연산에는 잘 익숙하지 않아서인 듯~~~

위의 경우를 더 확장해 특정 인덱스를 나머지 값을 산출해 역순으로 적용하는 경우
31 - (i % 32)  이런 식으로 표현하는데 (이경우 인덱스는 31, 30, 29,,,,,0 다시 이런 인덱스 반복~~~)
컴파일러는  31 - (i & 31) 이 정도의 최적화를 하고 아래와 같이 어셈블리화한다.

MOV ECX,1F
AND EDX,1F
SUB ECX,EDX

그런데 이 경우 ~i & 31 식으로 바꿀 수 있다. 정형화된 형태는 ~i & (2의 n제곱 -1) 이다.
NOT ECX
AND ECX,1F
두 줄이 된다.
확실히 실행시간이 더 단축되었다.