[C++] bit storage 작성 시 주의사항

pvs-studio ¹ 를 이용하여 레거시 코드를 검사했을 때 발견한 경고를 기반으로 구성했다.

다음 코드는 8byte bitSet 변수가 for 문의 loop를 돌 때마다 이진수로 표현했을 때 1, 11, 111, 1111, ….. 값이 되길 바라는 코드다. 64번째 돌았을 때 bitSet 변수가 2진수로 1이 64개가 있기를 바랬다.

	
typedef unsigned __int64 BitSetType;

	BitSetType bitSet = 0;
	for (int i = 0; i < 64; ++i)
	{
		BitSetType temp = 1 << i;
		bitSet |= temp;
	}

하지만 i 가 31이 된 루프에서 bitSet 변수는 1이 64개 모두 채워진다. 왜일까.

어셈블리 코드로 확인을 해보니

	
BitSetType temp = 1 << i;
 mov         eax,dword ptr [i]  
 mov         ecx,1  
 mov         dword ptr [rsp+18h],ecx  
 movzx       ecx,al  
 mov         eax,dword ptr [rsp+18h]  
 shl         eax,cl  
 cdqe  
 mov         qword ptr [temp],rax

7번 라인을 실행한 후 eax 가 0x80 00 00 00 값으로,
8번 라인의 cdqe² 명령이 eax(4바이트)를 rax(8바이트)로 변환하면서 sign extension³이 일어나 rax 의 상위 4바이트가 모두 1로 채워졌다.

sign extension 을 막기 위해 처음 코드로 돌아가 6번 라인을 다음과 같이 고쳐보았다.

BitSetType temp = 1u << i;

31번째 루프에서 더 이상 sign extension이 일어나지는 않는다. 하지만 64번 루프까지 모두 마쳤더라도 bitSet 변수는 모두 1로 채워지지 않는다. 이미 위의 어셈블리 코드에서 보고 알았겠지만 unsigned int (위에서는 1u) 를 갖고는 상위 4바이트를 1로 채울 수가 없다. 다음과 같이 변경해야 한다.

BitSetType temp = 1ull << i;

64번의 루프 동안 한 비트씩 잘 채워나가고 생성된 어셈블리 코드도 옳게 보인다.

BitSetType temp = 1ull << i;
 mov         eax,dword ptr [i]  
 mov         ecx,1  
 mov         qword ptr [rsp+18h],rcx  
 movzx       ecx,al  
 mov         rax,qword ptr [rsp+18h]  
 shl         rax,cl  
 mov         qword ptr [temp],rax

결론 : 웬만하면 std::bitset 을 사용하고, 필요하다면 shift 연산자의 왼쪽 값의 타입 지정할 때 주의하자.