C++ 왼쪽 비트 시프트 32

Question

현재 배낭 문제에 대한 무차별 대입 알고리즘을 연구 중입니다. 모든 것이 작은 문제 인스턴스 (예 : 15 개 항목)에 대해 완벽하게 작동합니다. 그러나 31 또는 32와 같은 더 큰 인스턴스에 대해 프로그램을 실행하면 알고리즘이 실패합니다. 가능한 솔루션 수를 계산할 때 사용하는 비트 단위의 시프트 문제가 발생했습니다. 예를 들어 10 개 항목으로 프로그램은 2^10 반복을해야하므로이 문을 사용합니다.

unsigned long long int setCnt = (1 << 10); 

계산 값은 1024입니다. 그러나 (1 << 31)의 경우 계산 된 값은 18446744071562067968 (최대 unsigned long long int)이지만 2147483648이어야합니다. (1 << 32)은 0을 반환합니다. 모든 것이 0에서 30 비트로 이동하는 데는 문제가 없습니다.

저는 Visual Studio 2015 Community를 사용하고 x64 모드로 솔루션을 컴파일하고 있습니다. 이 동작의 원인은 무엇입니까? 어떻게 이것을 피할 수 있습니까?

Answer 1

문제는 1이라고하는 signed int 문자 상수 - 그래서 변화는 (분명히 컴파일러의 기호를 포함하여 단지 32 비트 인)을 signed int 교대로 수행됩니다, 그래서 정의되지 않은 동작으로 이어지는, 오버 플로우.

1ULL << 32 (또는 다른 원하는 시프트 량)을 사용하십시오. ULL 접미어는 상수를 원하는 결과의 유형과 일치하는 unsigned long long으로 만듭니다. 시프트 양이 unsigned long long에 비해 너무 커지면 여전히 오버 플로우 될 수 있지만 그때까지는 작동합니다.