시프트 곱셈은 말 그대로 시프트를 이용한 곱셈이다.

시프트 연산은 정수에서만 가능하므로, 편하게 모든 타입을 unsigned int로 간주한다.


C언어에서 4 * 2는 4 << 1로 표현될 수 있다.

4: 100

2: 10

-> 8: 1000

4 << 1

100 -> 1000

이므로 4 << 1이다. 생각해 보면 십진수의 관점에선 19*10=190처럼 0이 포함된 만큼 숫자를 왼쪽으로 밀게 되므로, 2진수에도 똑같이 적용되어 밀릴 수 있는 것이다.


그럼 4*3은 어떻게 표현될까?

4: 100

3: 11

이다. 11은 0으로 이루어진 부분이 없기 때문에 나누어 준다.

3 = (1 + 2) = (1 + 10)

즉, 100 * 1 + 100 * 10이므로 (4 << 1) + 4와 같다.


4*7도 위와 같이 표현될 수 있을 것이다.

7: 1 + 2 + 4

이므로

100 * 1 + 100 * 10 + 100 * 100인 것이다.

(4 << 2) + (4 << 1) + 4

하지만 7과 8-1은 같으므로

(4 << 3) - 4 으로도 표현될 수 있다.


이렇듯 곱셈이 간단한 모양의 시프트 연산으로 바꾸어 질 수 있는 부분은 대부분 위와같이 최적화되어있다.

곱셈연산이 시프트 연산보다 몇 배로 비싸기 때문이 아닐까싶다.


--


이 이야기가 나온 이유는 밑에 적어놓은 

unsigned int what(unsigned int l, unsigned int r)

{

    unsigned int k;

    for(k = 0; r; l <<= 1, r >>= 1)

        k += r & 1 ? l : 0;

    return k;

}

이 함수에 대해 말할려고 해서이다. (조별과제에서 적절히 활용하자)

결론부터 말하면 이 함수는 l * r를 계산하는 함수이다.

이 함수가 어떻게 곱셈연산을 하는지는 위에 설명된 시프트 곱셈 연산과 원리가 같다.

단지 4를 l로 7을 r로 대신 표현한 것이다.


방법은 이렇다.

1. 일단 어떤 것을 시프트피연산자로 삼을지 정한다.

what함수의 경우엔 r 변수를 시프트피연산자로 강제하지만, 시프트 곱셈에선 한 쪽 피연산자는 상수다.

2. 이진수로 표현한다.

위에서 1011 같은 경우엔 켜진 비트만을 이용해 x << 3, x << 1, x와 같이 표현했다는 것을 이해했을 것이다.

즉, 켜진 n번째 비트들에 관해 x << n연산을 수행한다. (n=0,1,2,...)

3. 켜진 비트만 선별하여 덧셈연산을 반복한다.

And 0x1연산을 수행하여 비트가 켜져있는지 확인하면 된다.


첫 번째로 위 3가지를 이용해 구현한 함수이다.

k := 결과

t := 왼쪽 피연산자

j := 오른쪽 피연산자


for (k = 0, i = 0; i < sizeof(unsigned int) * 8; i++)

   if (j & (1 << i))

      k += t << i;


sizeof(unsigned int) * 8는 i가 32비트, 64비트 운영체제에서 각각 최대 31, 63번째 자리까지 볼 수 있게 놔둔것이다.

if (j & (1 << i))문은 i번째 비트가 켜져있는지 확인한다. 1 << i로 i만큼 1오른쪽에 0을 채우기 때문에 확인이 가능하다.

k += t << i는 4*3연산에서 (4 << 1) + (4 << 0)과 같이 시프트 연산후 더하는 구문을 루프문으로 바꾸기 위해 사용한 것이다.


두 번째로 위 함수를 약간 보기 좋게 바꾼 것이다.

for (k = 0, i = 0; j > 0; i++, j >>= 1)

   if (j & 1)

      k += t << i;

장점으론 마지막 비트까지 연산하지 않아도 0이 되면 종료할 수 있다느 점이다.


마지막으로 변수 i를 삭제하고 삼항 연산자를 사용해 축소한 것이다.

for(k = 0; j; i <<= 1, j >>= 1)

    k += i & 1 ? l : 0;