c언어 비트 이동 연산자 (<<, >>) : 어떤 것을 조심해야 할까요?

 어제, 비트 연산자 내용을 하면서 이런 이야기를 했을 거에요. >>와 <<는 다음에 정리하겠다. 사실, 그렇게 간단하지는 않습니다. 글 하나를 따로 빼야 할 정도로 내용이 어느 정도 있어요. 오늘은 이 둘의 동작에 대해서 C11에 나온 표준 문서를 토대로 정리해 보도록 하겠습니다. 혹여나, 이전에 제가 썼던 비트 연산자에 관한 글을 안 보셨다면, 보고 오시는 것도 괜찮을 듯 싶습니다.

 

 

[관련글]

[C] 비트 연산자 다져보자

---

 

 sizeof(int)가 32라고 해 봅시다. int형 변수 a를 선언했습니다. 이 때, a<<35의 결과값이나, a>>35의 결과값은 어떻게 나올까요? 혹은 a<<32나, a>>32, a<<(-1), a>>(-1) 이러한 것들 말입니다. 일단 음수만큼 shift를 시키는 것은 undifined behavior입니다. 그러니, 그 경우에는 볼 필요도 없어요.

 

 

 코드는 다음과 같아요. arr[0]에는 5를, arr[1]부터 arr[9]까지는 i + 16을 넣었습니다. 저는 arr[0]<<32의 값과, arr[1]>>32의 값을 구하려고 하는데요. 이 환경에서는 int형이 4byte입니다. 4byte는 32bit입니다. 이걸 그대로 컴파일을 하면, 좌측 연산자의 width보다 크거나 같기 때문에 warning이 뜰 건데요.

 

 

 제 리눅스 환경에서, arr[0]<<32와, arr[1]>>32를 연산한 결과는 아래와 같습니다.

 

 

 재미로, arr[2]>>33을 하면 어떤 값이 나오는지도 봅시다.

 

 

 잘 모르겠네요. 표준에서는 이러한 연산의 결과는 정의되지 않는다고 이야기 합니다. 정리하면, a가 int형이라면, b가 sizeof(int)보다 같거나 큰 경우에 (a<<b)의 결과값과 (a>>b)의 결과값은 정의되지 않습니다. 이런 실수는 보통 하지 않으시니까, 넘어가도록 하겠습니다.

 

 

---

 먼저 a<<b인 경우를 봅시다. 이것은 bit를 b만큼 왼쪽으로 shift하라는 겁니다. 예를 들어서, b가 1이라고 생각해 봅시다. 그리고 a가 1입니다.

 

 

 그러면 a<<1은 왼쪽으로 1칸만큼 옮기라는 것이니까, 요래 될 겁니다.

 

 

 이 ?부분은 0으로 채워집니다. 즉, 왼쪽으로 1칸만큼 이동했기 때문에 비워진 (vacated) 비트는 빨간색으로 표시된 부분인데요. 이 부분의 비트값이 0으로 채워집니다. 즉, 기본적으로 a<<b는 a에다가 2^b를 곱한 값 v와 같습니다. 이것은 signed나, unsigned나 같습니다. unsigned인 경우 먼저 봅시다.

 

 만약에 unsigned 형이라면, 부호 bit를 쓰지 않습니다. 그렇기 때문에 만약에 sizeof(int)가 4라면, int형이 표현할 수 있는 범위는 0부터 2^32-1인 4294967295까지일 겁니다. 만약에 a가 unsigned int형이였고, 그 값이 3이였다고 해 봅시다. 그러면 a는 이렇게 표현이 될 겁니다.

 

 

 그리고 31만큼 left shift를 했다고 해 봅시다. v의 값이 4294967295보다 작거나 같았다면 v가 나옵니다. 만약에 v의 값이 그 값보다 크면 어떻게 될까요? 이 때에는 오버 플로우가 일어나게 되는데요. 표준에 따르면, 그 값에 one more than maximum value를 모듈러를 취한 값이 나온다고 되어 있어요. 즉, sizeof(int)의 값이 32라면, 결과 값이 u bit로 표현된다면, 거기에서 하위 32비트만 취한다는 소리입니다.

 

 

 그런데, 만약에 signed type이라면 어떨까요? 이 때에는 최상위 비트가 0인 경우와 그렇지 않은 경우로 나뉩니다.

 

 

 먼저 부호 비트가 0이면서 a에 2^b를 곱한 값이 표현 가능한 범위 내에 있으면 (a<<b)의 값은 a에 2^b를 곱한 값이 됩니다. 하지만, 그 범위 내에 있지 않으면 결과가 정의되지 않습니다. 부호 비트가 1이라면 어떨까요?

 

 

 

 예를 들어서, a가 -2라고 해 봅시다. (-2<<2)의 값은 무엇이 나올까요? 이 때는 행동이 정의되지 않습니다. 어떻게 나올지 잘 모른다는 것입니다. 정리해 봅시다. 만약에 a<<b에서 a가 unsigned형이라면, 문제는 없습니다. 설령 a에 2^b를 곱한 값이 그 자료형이 표현할 수 있는 범위를 넘어선다고 한다고 해도, 표현 가능한 범위에 1을 더한 값을 모듈러 한 값을 뱉습니다.

 

 그런데, a가 signed라면, a에 2^b를 곱한 값이 자료형이 표현할 수 있는 범위를 넘어서지 않고, 음수가 아니라면 a에 2^b를 곱한 값이 나와요. 그렇지 않다면 undefined behavior에요. 이 부분은 조심하셔야 합니다. 저는 습관적으로 int형으로 평가되는 1에다가 31을 왼쪽으로 shift 하는 습관이 있는데, 상태 수가 32개다. 그리고 31만큼 왼쪽으로 shift를 해야 한다. 그러면 그냥 조용히 a를 long long형으로 선언한 다음에 (a<<31); 을 해주시는 게 안전할 듯 싶습니다. 보통 ps에서는 많아봤자 상태 수가 20이고, 40개라면 meet in the middle로 20개씩 쪼개니까, 별 문제는 없을 겁니다. 그냥, 범위가 넘어갈 거 같다. 싶으면 자료형의 크기를 늘리는 게 좋아요.

 

 

---

 a>>b의 값은 어떨까요? 이 부분도 크게 어렵지 않아요. unsigned이거나, signed이지만, 부호 비트가 0인 경우에는 말 그대로, 오른쪽으로 b만큼 shift를 시킵니다.

 

 

 a>>29의 값은 어떻게 될까요?

 

 

 오른쪽으로 shift 했다면 ?를 채워야 할 건데요. 빨간 부분은 0으로 채워집니다. 따라서, a>>b의 값은 a에다가 2^b를 나눈 몫이 됩니다. 그런데, a가 signed이면서, 음의 정수인 경우에는, 결과 값이 implement defined인데요. 이는 환경에 따라서 결과 값이 달라진다는 이야기입니다. 예를 들어서, -2147483648을 생각해 봅시다.

 

 

 a와 a를 오른쪽으로 10만큼 이동시킨 것이랑 출력을 해 보겠습니다.

 

 

 제 시스템에서는 1이 채워집니다. 하지만 환경에 따라서는 0이 채워질 수도 있습니다. 이 부분은 필히 조심하셔야 합니다. >> 연산자는, signed형이면서, 부호 비트가 1인 경우에, 결과값이 implement defined가 된다. 정도만 보시면 좋을 듯 싶습니다.