비트 이동 연산자 ( << , >> ) 의 결과

재미있는 글을 보고서.. 나도 포스팅

알다시피, 비트연산자 << n 은 n 비트 만큼 왼쪽으로, >> n 은 n 비트만큼 오른쪽으로 비트를 이동(shift) 한다는 의미이다.

예를 들어,
int n = 1;
n =<< 1;
위와 같이 하면 n 의 값은 1 비트씩 왼쪽으로 밀려서 답이 2 가 된다.
( 일반적으로 2^n 값을 곱하거나 나눌 때, 비트 연산자를 종종 활용한다. 비트연산의 장점은 비트 단위에서 직접 조작하므로 일반 사칙연산보다 더 빠르다는 것.. 단, 이러한 연산법은 양수일 경우에만 제대로 동작한다. 자세한 내용은 아래 다시 설명 )

그러다면 아래와 같은 비트 연산의 결과는 어떻게 될까?
( 테스트 환경은 Intel 계열 CPU )

Quiz 1)
int n = 1;
n =<< 31;
cout << n << endl   // n 은 얼마??

Quiz 2)
int n = 1;
n =<< 32;
cout << n << endl   // n 은 얼마??

Quiz 3)
int n = 1;
n =<< 33;
cout << n << endl   // n 은 얼마??

Quiz 4)
int n = -2;
n =<< 31;
cout << n << endl   // n 은 얼마??

Quiz 5)
int n = -256;
n =>> 31;
cout << n << endl   // n 은 얼마??

Quiz 6)
int n = -256;
n =>> 33;
cout << n << endl   // n 은 얼마??

Quiz 7)
int n = 1;
n <<= -123;
cout << n << endl   // n 은 얼마??


 C99 표준문서 의 6.5.7 Bitwise shift operators 를 보면 다음과 같이 정의되어 있다.
If the value of the right operand is negative or is
greater than or equal to the width of the promoted left operand, the behavior is undefined.

The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are filled with
zeros. If E1 has an unsigned type, the value of the result is E1 * 2^E2, reduced modulo
one more than the maximum value representable in the result type. If E1 has a signed
type and nonnegative value, and E1 * 2^E2 is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.

The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type
or if E1 has a signed type and a nonnegative value, the value of the result is the integral
part of the quotient of E1 / 2^E2. If E1 has a signed type and a negative value, the
resulting value is implementation-defined.

우측 피연산자 값이 음수이거나 좌측 피연산자의 범위보다 큰 경우의 행위는 정의되지 않았다 (undefined)

E1 이 양수인 경우에는 E1 << E2 는 E1 을 E2 비트만큼 왼쪽으로 이동, 이 것은 E1 에 2^E2 을 곱한 것과 같다. E1 이 음수인 경우의 동작은 정의되지 않았다.
E1 이 양수인 경우 E1 >> E2 역시 E1 을 E2 비트만큼 오른쪽으로 이동, 이것은 E2 를 2^E2 를 나눈 것과 같다. 그러나, E1 이 음수인 경우, 결과는 구현에 따라 달라진다 (implementation-defined)

결국, C99 표준에 정의되지 않은 사항은 CPU 명령어 정의에 따라 달라지게 되는데... Intel CPU 에서의 동작은 다음과 같다.

우선, << , >> 연산자의 오른쪽 피연산자는 short 일때 4 자리(0 ~ 15까지), int 일때 5 자리(0 ~ 31 까지), 64 비트형인 long long 일때 6 자리 (0 ~ 63 까지) 의 범위에 대해서만 유효하다. 다시 말하면 오른쪽 피연산자는 short 일때 하위 4 비트만 사용하며, int 일때 하위 5 비트만 사용하며, long long 일때 하위 6 비트만 사용한다. 쉬프트 연산은 왼쪽 피연산자 값의 범위 (비트 길이) 내에서만큼만 쉬프트 연산이 이루어진다. 즉, Quiz 2 의 n <<= 32 에서 32 는 100000 이 되고, 하위 5 비트는 00000 이므로 n <<= 32 는 n <<= 0 과 같다. Quiz 3 의 n <<= 33 는 33 이 100001 이며 이중 하위 5 비트는 00001 이므로 n <<= 33 은 n <<= 1 과 같아지는 것이다.

n << x 이면 일반적으로는 n 이 2^x 만큼 곱한 것과 같아지게 되는데, Quiz 1 의 경우는 1 << 31 의 답이 1 * 2^31 이 아닌 -2147483648 ( -1 * 2^31 ) 이 된다. 이렇게 되는 이유는 int 의 경우 최상위 비트가 부호 비트가 되어 부호 비트가 0 에서 1 로 바뀌면서 음수값을 취하게 되기 때문이다. ( 최상위비트 참고 )

Quiz 1 의 결과
00000000 00000000 00000000 00000001 // 1 을
10000000 00000000 00000000 00000000 // 31 만큼 좌측을 이동, 부호 비트가 1 이 되며 답이 -2147483648
만약 n 이 unsigned int 였다면, 답은 양의 정수 2147483648 이 된다.

Quiz 2 의 결과
00000000 00000000 00000000 00000001 // 1 을
00000000 00000000 00000000 00000001 // <<= 32 는 <<= 0 과 같으므로, 결과는 변함 없어 답은 1

Quiz 3 의 결과
00000000 00000000 00000000 00000001 // 1 을
00000000 00000000 00000000 00000010 // <<= 33 는 <<= 1 과 같으므로, 결과는 1 비트 좌측이동하여 답은 2

Quiz 4 의 결과
11111111 11111111 11111111 11111110 // -2 을
00000000 00000000 00000000 00000000 // <<= 31 로 31 만큼 좌측 이동. 결과는 0 이 된다.

왼쪽 피연산자가 음수인 경우에 << 의 경우는 왼쪽으로 비트를 이동하면서 0 으로 채운다. 그런데, implementation-defined 되 있는 >> 연산자는 동작방식이 다르다.
 << 연산자의 경우 양수/음수 모두 이동한 자리를 0 으로 채운다. 반면에 >> 연산자의 경우 양수일 경우에는 오른쪽으로 비트를 이동하면서 이동한 자리는 0 으로 채우는데, 음수일 경우에는 이동한 자리를 1 로 채우게 된다. 그래서 Quiz 5 의 경우 오른쪽으로 이동하고 난 후의 남은 31개 비트를 모두 1 로 채우므로 답은 -1 이 된다.

Quiz 5 의 결과
11111111 11111111 11111111 00000000  // -256
11111111 11111111 11111111 11111111  // 31 만큼 우측 이동, 음수의 경우 이동한 자리는 1 로 채워짐. 답은 -1

Quiz 6 의 결과
11111111 11111111 11111111 00000000  // -256
11111111 11111111 11111111 10000000  // 33 만큼 우측이동, >> 33 은 >> 1 과 같아서 답은 -128

>> 연산자 역시 << 연산자와 마찬가지로 int 의 경우 오른족 피연산자의 하위 5 비트에 해당하는 값만큼만 이동을 한다. 그러므로 int n 의 경우 n =>> 33 은 n=>> 1 과 같아진다.

음수일 경우 >> 연산을 하여 이동한 자리를 0 이 아닌 1 로 채우는 이유는 아마도 n =-2, n  >>= 1 일때  n = -1 이 되는 것과 같이 음수인 경우 나눗셈 연산이 정상적으로 동작하도록 하게 하려는 의도였을 것이다.
하지만 음수는 2 의 보수로 계산되기 때문에 음수인 경우에는 n 비트 쉬프트 연산의 결과가 2^n 곱셉/나눗셈의 결과와는 동일하게 동작하지 않는 경우도 종종 생긴다. ( 2^n 꼴의 수가 아닌 경우 이러한 경우가 발생 )
예를 들면 n = -10 일때 n =>> 3; 의 결과는 n /= 8; 과는 다른 결과가 나온다. 
( n =>> 3 이면 n = -2, n /= 8 이면 n = -1 )

11111111 11111111 11111111 11110110   // -10
11111111 11111111 11111111 11111110   // 우측으로 3 비트 이동한 후의 결과, -2 가 됨

끝으로, Quiz 7 과 같이 쉬프트 연산에 있어서 오른쪽 피연산자의 값이 음수일 경우 역시 오른쪽 피연산자의 하위 5 개 비트의 값에 해당하는 크기만큼만 비트 이동을 하므로, -123 이 11111111 11111111 11111111 10000101 이며 이중 하위 5 비트는 00101 이므로 결국 n <<= -123 은 n <<= 5 와 같다.
그러므로 1 <<= 5 한 결과는 32.

비트연산은 다양한 최적화 테크닉에 있어 중요한 부분을 차지하고 있고, 의외로 많은 사람들이 헷갈려 하는 부분이당( 나 포함 )...