쉬프트 연산과 곱셈

쉬프트 연산과 곱셈

비트를 이동시키는 쉬프트 연산은 곱셈과 나눗셈의 대용으로 사용할 수 있다. 다음 예제를 실행해 보아라.

 

예 제 : shiftmulti

#include <Turboc.h>

 

void main()

{

     int i;

 

     printf("정수를 입력하세요 : ");

     scanf("%d",&i);

     printf("결과=%d\n",i << 1);

}

 

정수 i를 입력받은 후 왼쪽으로 한칸 쉬프트한 값을 출력했다. 실행해 보면 알겠지만 입력한 수의 정확하게 2배되는 값이 출력된다. 5를 입력하면 10, 100을 입력하면 200이 출력될 것이다. 정수를 왼쪽으로 한칸 쉬프트하면 두배가 되며 오른쪽으로 한칸 쉬프트하면 절반이 되는데 어째서 그런지 보자. 입력값이 5였다고 가정하면 이 값은 이진수로 0101인데 이 값을 10진수로 바꾸는 공식은 다음과 같다.

 

1*2²+0*2¹+1*2⁰ = 5

 

이진수의 각 자리수는 2의 거듭승에 해당하는 값을 표현한다. 그런데 비트를 왼쪽으로 한칸 이동시키면 모든 자리수의 지수가 1 올라가기 때문에 2배가 된다. 쉬프트한 결과는 1010이며 이 값은 다음과 같이 10진수로 바꿀 수 있다.

 

1*2³+0*2²+1*2¹+0*2⁰ = 10

 

그래서 왼쪽으로 한칸 쉬프트하면 두배가 되는 것이다. 단, 용량 한계를 넘어서는 값은 잘려 나가는데 이는 어쩔 수 없다. 예를 들어 16비트 정수 40000을 왼쪽으로 쉬프트하면 80000이 되는데 16비트로는 이 값을 표현할 수 없으므로 제일 오른쪽의 1이 밀려나고 결과는 14464가 된다. 이 값은 80000-65536인데 밀려나서 버려진 오른쪽 비트의 값이 65536이기 때문이다. 32비트의 int형을 쓰면 웬만큼 큰 수라도 용량의 한계를 넘지 않을 것이다.

왼쪽으로 쉬프트하는 연산이 값을 두배로 만드는데 비해 오른쪽으로 쉬프트하는 연산은 값을 절반으로 만든다. 모든 자리수의 지수가 1 감소하기 때문이다. 이진수 1100을 오른쪽으로 쉬프트하면 0110이 되는데 이 값은 처음값 12의 절반인 6이다. 동일한 원리이므로 따로 그림까지 그릴 필요는 없을 것 같다.

오른쪽 쉬프트는 자리 넘침이 발생하지 않지만 오른쪽으로 밀려나 사라지는 값만큼 오차가 생길 수는 있다. 짝수를 밀면 정확하게 절반이 되지만 홀수를 밀면 제일 오른쪽에 있던 1이 밀려 나므로 실제값보다 0.5더 작은 값이 계산된다. 예를 들어 이진수 0111(7)을 오른쪽으로 밀면 b0가 밀려나고 0011(3)이 된다. 정확하게 계산하자면 3.5가 되어야 하지만 비트는 정수의 세계이기 때문에 밀려난 0.5는 사라지게 된다.

좌우 쉬프트 연산이 곱셈과 나눗셈 대용으로 사용될 수 있다는 것이 도저히 이해가 안간다면 아마도 2진수에 익숙하지 않아서 그럴 것이다. 그렇다면 10진수로 이 현상을 설명해 보자. 10진수 1234에서 각 자리수는 10의 거듭승에 해당하는 자리값을 가지고 있다. 1은 10³인 1000자리에 있고 2는 10²인 100자리에 있고 3은 10¹인 10자리에 있는 셈이다.

 

1234=1*10³+2*10²+3*10¹+4*10⁰

 

이 값을 왼쪽으로 쉬프트하면 각 자리수의 지수가 1증가한 12340이 된다.

 

12340=1*10⁴+2*10³+3*10²+4*10¹+0*10⁰

 

천자리는 만자리로 올라가고 백자리는 천자리로 올라가므로 모든 값이 10배가 되어 전체값도 10배가 되는 것이다. 반대로 오른쪽으로 밀면 모든 자리수가 10배 감소하므로 10분의 1로 값이 줄어든다. 1234를 오른쪽으로 밀면 123이 되고 일자리에 있던 4는 밀려나 사라진다. 물론 실수 차원이라면 123.4가 되겠지만 말이다.

좀 더 쉽게 설명하자면 임의의 십진수가 있을 때 뒤에 0을 하나 더 붙이면 10배가 되고 제일 뒷자리를 제거해 버리면 약간의 오차를 제외하고 1/10로 그 값이 줄어든다. 초등학생들도(심지어 일부 유치원 아동들까지도) 아는 간단한 원리이며 일상 생활에서도 흔히 있는 연산이므로 너무 너무 당연하게 생각될 것이다. 10진수에서 쉬프트 연산이 10배씩 증감하는 것처럼 2진수에서는 쉬프트 연산이 2배씩 증감하는 것이다.

왼쪽으로 한칸 밀면 두 배가 된다. 그럼 이 수를 다시 왼쪽으로 한칸 밀면 2배의 2배, 즉 4배가 될 것이다. 다시 한 번 더 밀면 8배가 된다. 자, 그럼 이제 쉬프트 연산과 곱셈 연산의 관계를 일반화해 보자.

 

a << b == a * 2^b

 

a를 b만큼 왼쪽으로 민다는 것은 a를 2의 b승만큼 곱하는 것과 같다. 이 공식은 b가 음수일 때도 똑같이 적용된다. a를 -1만큼 왼쪽으로(즉 오른쪽으로 한칸) 밀면 2^-1를 곱하는(즉 2로 나누는)것과 같다. 그래서 곱셈 대신에 쉬프트 연산을 사용할 수 있는데 이 두 연산은 엄청난 속도 차이가 있다. 비트를 이동시키는 것과 일정 횟수 더하기를 반복하는 것은 CPU 입장에서 보면 완전히 다른 작업이기 때문에 속도차가 무려 10배 정도 난다. 쉬프트 연산은 전혀 논리적이지 않으며 기계적이므로 기계가 하기에는 아주 쉬운 연산인 것이다.

즉 a*2를 한 번 할 시간이면 a << 1을 10번 정도 할 수 있다는 얘기다. 이렇게 속도차가 나기 때문에 핵심 게임 엔진이나 시스템 프로그래머들은 곱셈 대신 쉬프트 연산을 즐겨 사용한다. 중요한 루프에서 곱셈을 하느냐 쉬프트 연산을 하느냐에 따라 프로그램의 성능에 확연한 차이가 나기 때문에 쉬프트 연산은 도저히 피할 수 없는 달콤한 유혹인 것이다.

쉬프트 연산이 곱셈에 비해 불리한 점은 2의 거듭승에 대해서만 곱셈이 가능하다는 점이다. 2배, 4배, 8배, 16배 등만 할 수 있으며 3배, 17배 이런 연산은 할 수 없다. 그러나 쉬프트 연산과 덧셈, 뺄셈을 잘 조합하면 이런 연산이 가능해지기도 한다.

 

3배 : a << 1 + a;

9배 : a << 3 + a;

15배 : a << 4 - a;

60배 : a << 6 - a << 2;

 

특히 제일 마지막의 쉬프트 연산으로 60배를 하는 코드는 아주 기발한 응용예이며 감탄을 금하기 어려운 예술 코드라고 할 수 있다. 정밀하게 측정해 보면 이런 연산들이 곱셈보다 수배~수십배 더 빠르다. 보통의 경우라면 일반적인 곱셈을 하는 것이 소스를 유지하기에 편리하지만 속도가 지극히 중요하다면 곱셈보다는 가급적이면 쉬프트 연산을 사용하는 것이 좋다.

[출처] 쉬프트 연산과 곱셈|작성자 청주콜라