[asm] shift 이용한 2로 나누기

어셈블리 코드를 보면 나눗셈 명령대신 bit shift 를 많이 사용하는 것을 알 수 있다. 이것은 bit 가 가지는 독특한 특성 때문인데, 자리수가 하나 늘어나면 십진수로는 2배가 되기 때문이다.

다음과 같이 십진수와 2진수를 비교해 보자.

Decimal	0	1	2	3	4	5	6	7	8
Binary	0000	0001	0010	0011	0100	0101	0110	0111	1000

2와 4 , 4와 8을 자세히 보자. 2는 0010, 4는 0100 이다. 자리수가 하나 늘어났다. 그리고 이것은 어떻게 보면 왼쪽으로 한자리 이동(shift left) 한 것과 같다. 즉, 곱셈 대신 shift left 하면 곱하기 2가 된다. 반대로 생각하면 shift right 하면 나누기 2가 된다. 어셈블리어로 이것을 표현하면 다음과 같이 된다.

shr eax, 1

eax 의 값을 한자리 오른쪽으로 이동시키라는 명령이다. shr 은 bit shift 명령으로 옮기고 난 빈 자리는 0으로 clear 해 버린다. 그런데 이것은 음수의 경우에는 문제가 있다. 음수의 경우에는 MSB(Most Significant Bit) 즉, 가장 왼쪽 비트가 1이다. 이걸 오른쪽으로 밀어내면서 0으로 채우면 이제부터는 양수가 되어 버리는 것이다. -4 를 예로 들어 보자. -4를 2로 나누면 -2 가 되어야 한다. 하지만 shr eax, 1 해버리면 결과값은 2147483646 이 되어버린다. 전혀 엉뚱한 값이 나오는 것이다. -4 를 비트로는 어떻게 표현할까? 일단 4를 비트로 표현해 보자.

32비트 값으로 8비트씩 끊어서 표현하면

00000000 00000000 00000000 00000100

-4 는 각 비트를 invert 시키고 1을 더하면 된다.

11111111 11111111 11111111 11111100

eax 에 위와 같은 값이 있다고 가정하고 shr 로 1비트 오른쪽으로 이동하면 즉, shr eax, 1 하면

01111111 11111111 11111111 11111110

MSB 가 0이므로 더이상 음수가 아니다. 부호 비트를 제외한 나머지 31비트만 생각하면 31비트를 모두 1로 채우는 것보다 1이 작으므로 즉, 2³¹ -1 이다. 2³¹ = 2147483647 이므로 2³¹ -1 = 2147483646 이 되는 것이다. 이제, 음수를 2로 나누는 용도로는 shr 를 사용하면 안된다는 것을 알 수 있다. 그럼 어떤 명령을 사용해야 할까? 음수의 경우에는 SAR(Shift Arithmetic Right) 를 사용해야 한다. sar 은 최상위 비트(MSB)를 부호비트로 채우면서 오른쪽으로 이동한다. 양수의 경우라면 0으로 채우면서 이동하고 음수의 경우에는 1로 채우면서 이동한다. 즉, 다음과 같이 이동한다.

그러므로 음수의 경우는 sar eax, 1 로 하면 -4 가 -2 로 된다.

그런데 shift 명령을 이용한 음수 나눗셈은 짝수인 경우에는 IDIV(Signed Divide) 명령과 같은 결과를 보여주지만 홀수의 경우에는 약간 다른 결과를 보여준다. IDIV 명령은 몫을 반올림 할때 (round) 소수점 이하를 0으로 만들지만 SAR 명령은 음의 방향으로 반올림을 해버린다.  -9 를 2로 나누면 -4.5 가 된다. 이걸 정수로 표현할 때 IDIV 는 소수점 이하를 버려서 -4 가 되고 SAR 은 음의 방향으로 반올림이 일어나서 -5 가 된다. shift 가 나눗셈 명령보다는 빠르고 간편하지만 상황에 따라서 선택해야 한다.