예기치 않은 C/C++ 비트 시프트 연산자 결과

Question

나는 이것으로 정신 나간다고 생각합니다.

결과로 N 비트가 1로 설정된 (부호없는) 정수를 생성해야하는 코드 조각이 있습니다. 정확하게 비트 마스크가 있고 어떤 경우에는 솔리드 한 값으로 설정하고 싶습니다. .

I 다음 함수가 :

void MaskAddRange(UINT& mask, UINT first, UINT count) 
{ 
    mask |= ((1 << count) - 1) << first; 
} 

간단한 즉

바이너리 표현 1 << count은 다수 011...111 제공 등으로부터 1을 감산 (제로의 개수 count이다) 100...000이며 우리 단지 왼쪽 다음을 first까지 이동하십시오.

에서 다음 명백한 제한이 충족 될 때 위의 올바른 결과를 산출한다 : 그것은 는 "극단적 인"경우에 제대로 작동합니다 것을

first + count <= sizeof(UINT)*8 = 32

참고.

• 우리가 (1 << count) = 1이 count = 0 경우, 따라서 ((1 << count) - 1) = 0. 최고의 비트 오버 플로우 때문에, 및 C/C++에 따라 우리가 (1 << count) = 0이 count = 32 경우
• 는, 비트 시프트 연산자는 순환하지 이다 규칙. 그런 다음 ((1 << count) - 1) = -1 (모든 비트가 설정 됨).

그러나, 밝혀진 바와 같이, count = 32에 대해서는 공식이 예상대로 작동하지 않는다. 발견 된대로 :

UINT n = 32; 
UINT x = 1 << n; 
// the value of x is 1 

또한 MSVC2005 IDE를 사용하고 있습니다.

mov eax,1 
mov ecx,dword ptr [ebp-0Ch] // ecx = n 
shl eax,cl     // eax <<= LOBYTE(ecx) 
mov dword ptr [ebp-18h],eax // n = ecx 

참으로 마법 없다 : 나는 디버거에서 위의 식을 계산할 때, 그 결과는 내가 x 우리는 다음을 참조 디스어셈블러를 통해 1 lokking 있습니다의 값을 가져옵니다, 위의 라인을 통해 단계 그러나 경우 0입니다 , 컴파일러는 shl 명령어를 사용했습니다. 그렇다면 shl은 내가해야 할 일을하지 않는 것 같습니다. CPU가이 명령을 무시하기로 결정했거나 시프트가 32를 기준으로 처리되거나 donno가 처리됩니다.

내 질문은 :

• shl/shr 지침의 올바른 행동이 무엇입니까?
• 비트 시프트 명령어를 제어하는 ​​CPU 플래그가 있습니까?
• C/C++ 표준에 따른 것입니까? 사전에

감사

편집 : 답변

감사합니다.나는 (1) shl/shr 실제로 피연산자 modulo 32 (또는 & 0x1F)를 취급하고 (2) C/C++ 표준은 교대를 31 비트 이상으로 정의되지 않은 행동으로 취급 함을 깨달았다.

그런 다음 질문이 하나 더 있습니다. 이 극단적 인 경우를 다루기 위해 어떻게 "마스킹"표현식을 다시 작성할 수 있습니까? 분기하지 않아야합니다 (if, ?). 가장 단순한 표현은 무엇입니까?

Answer 1

1U << 32은 unsigned int이 32 비트 너비 인 경우 C 및 C++에서 정의되지 않은 동작입니다.

(C11, 6.5.7p3) "오른쪽 피연산자의 값이 음수인지, 동작이 정의되지 이상의 승격 왼쪽 피연산자의 폭과 동일하면"

(C를 + +11, 5.8p1) "오른쪽 피연산자가 음수이거나 승격 된 왼쪽 피연산자의 비트 길이보다 크거나 같으면 동작이 정의되지 않습니다." 당신이 이동하고있는 정수 타입에 비해 많은 이상의 비트가 쉬프트

Answer 2

C 및 C++에서 정의되지 않은입니다. x86 및 x86_64에서, 시프트 명령어의 시프트 양은 실제로 모듈로 32 (또는 오퍼랜드 크기가 무엇이든간에)로 취급됩니다. 그러나 은 컴파일러가 명시 적으로 해당 설명서에서 명시하지 않는 한 컴파일러가 C 또는 C++ >>/<< 조작에서 생성 한이 모듈러스 동작을 사용해서는 안됩니다.

Answer 3

요구 사항을 이해했다면 상위 N 비트가 설정된 부호없는 int가 필요합니까?

원하는 결과를 얻는 방법에는 여러 가지가 있습니다. 편집 : 나는이 밤은 매우 강력하고, n은> 32 실패 할 걱정이 매우 빨리 데이터의 132 바이트로해야

uint32_t set_top_n(uint32 n) 
{ 
    static uint32_t value[33] = { ~0xFFFFFFFF, ~0x7FFFFFFF, ~0x3FFFFFFF, ~0x1FFFFFFF, 
            ~0x0FFFFFFF, ~0x07FFFFFF, ~0x03FFFFFF, ~0x01FFFFFF, 
            ~0x00FFFFFF, ~0x007FFFFF, ~0x003FFFFF, ~0x001FFFFF, 
            // you get the idea 
            0xFFFFFFFF 
            }; 
    return value[n & 0x3f]; 
} 

.

강력하게하려면 모든 값을 63까지 늘리거나 조건부로 만들어야합니다.이 경우 원래 비트 마스킹 버전과 32 가지 경우 모두 수행 할 수 있습니다. 나는.

Answer 4

1 << 32은 1 << 0과 같다고 생각합니다. IA-32 인스트럭션 세트 레퍼런스 (Instruction Set Reference)는 시프트 인스트럭션의 카운트 피연산자가 5 비트로 마스크된다는 것을 나타냅니다.

IA-32 아키텍처의 명령어 세트 참조는 here입니다.

이

void MaskAddRange(UINT *mask, UINT first, UINT count) { 
    int count2 = ((count & 0x20) >> 5); 
    int count1 = count - count2; 
    *mask |= (((1 << count1) << count2) - 1) << first; 
} 

기본적인 아이디어는되도록 교대 작업을 분할하는 것입니다

는

는 "극단적 인"사건을 해결하려면 , 나는 단지 조금 어색 할 수있는 다음 코드 (아마도 버그)와 함께 올 수 각 시프트 수가 31을 초과하지 않습니다. 위의 코드는 카운트가 0..32 범위에 있다고 가정하므로 매우 견고하지 않습니다.

Answer 5

내 32 센트 :

#include <limits.h> 

#define INT_BIT  (CHAR_BIT * sizeof(int)) 

unsigned int set_bit_range(unsigned int n, int frm, int cnt) 
{ 
     return n | ((~0u >> (INT_BIT - cnt)) << frm); 
} 

^{목록 1.}

가짜/반원형 결과에 안전한 버전이 될 수있다 :

unsigned int set_bit_range(unsigned int n, int f, int c) 
{ 
     return n | (~0u >> (c > INT_BIT ? 0 : INT_BIT - c)) << (f % INT_BIT); 
} 

^{목록 2.}

분기없이 이렇게, 또는 지역 변수, 같은 수 있었다;

return n | (~0u >> ((INT_BIT - c) % INT_BIT)) << (f % INT_BIT); 

^{목록 3.}

목록이 및 목록 3이 줄 같은 긴 from로 결과를 "수정"할 미만 INT_BIT 및> = 0 즉 :

./bs 1761 26 810 
Setting bits from 26 count 810 in 1761 -- of 32 bits 
Trying to set bits out of range, set bits from 26 to 836 in 32 sized range 
x = ~0u  = 1111 1111 1111 1111 1111 1111 1111 1111 

Unsafe version: 
x = x >> -778 = 0000 0000 0000 0000 0000 0011 1111 1111 
x = x << 26 = 1111 1100 0000 0000 0000 0000 0000 0000 
x v1 Result = 1111 1100 0000 0000 0000 0110 1110 0001 
Original:  0000 0000 0000 0000 0000 0110 1110 0001  

Safe version, branching: 
x = x >> 0 = 1111 1111 1111 1111 1111 1111 1111 1111 
x = x << 26 = 1111 1100 0000 0000 0000 0000 0000 0000 
x v2 Result = 1111 1100 0000 0000 0000 0110 1110 0001 
Original:  0000 0000 0000 0000 0000 0110 1110 0001  

Safe version, modulo: 
x = x >> 22 = 0000 0000 0000 0000 0000 0011 1111 1111 
x = x << 26 = 1111 1100 0000 0000 0000 0000 0000 0000 
x v3 Result = 1111 1100 0000 0000 0000 0110 1110 0001 
Original:  0000 0000 0000 0000 0000 0110 1110 0001 

Answer 6

shift 작업을 두 단계로 나누면 정의되지 않은 동작을 피할 수 있습니다. 첫 번째 것은 (count - 1) 비트 그리고 두 번째 것은 1 비트 더. 케이스 카운트가 0 인 경우 특별한주의가 필요합니다 :

void MaskAddRange(UINT& mask, UINT first, UINT count) 
{ 
    if (count == 0) return; 
    mask |= ((1 << (count - 1) << 1) - 1) << first; 
}