비트 연산 : fitsBits 기능

Question

는이 사이트에이 기능의 몇 가지 다른 구현을 봐 왔지만, 누군가가 나를 알아내는 데 도움이 할 수있는 경우이 구현은 작동하지 않는 이유가 궁금 : 그래서

//fitsBits: return 1 if x can be represented as an n-bit, two's complement integer. 
//1<=n<=32 
//Examples: fitsBits(5,3)=0, fitsBits(-4,3)=1 
//legal ops: ! ~ &^| + << >> 
//Max ops: 15 

    int fitsBits(int x, int n) { 
     int mask = ~(1<<31); 
     return !(((x>>1)&mask)>>(~(~n+2)+1)); 
    } 

당신은 내 논리를 조금 따라갈 수 있습니다, 나는 잠재적으로 여분의 1 (산술 이동)을 노출시킬 수있는 오른쪽으로 한 x 이동합니다. 그래서 나머지 x를 이동하기 전에 마스크가 0인지 확인합니다. 원래는 x n 배를 오른쪽으로 이동해야하고, 1 초 이상 남아 있으면 x가 n 비트가 맞지 않는다는 것을 의미합니다. x를 오른쪽으로 1 비트 이동 했으므로 이제 n-1 번 이동해야합니다.

내가 얻는 결과는 : 당신이 - 제가 숫자에 대한 권리 변화는 "구현 정의"하는 C와 같은 외모를 서면으로 작성했습니다, 그래서 또는 산술 변화하지 않을 수 있습니다 무엇

ERROR: Test fitsBits(2147483647[0x7fffffff],31[0x1f]) failed... 
...Gives 1[0x1]. Should be 0[0x0] 

Answer 1

. (왼쪽 교대 일 경우 상황이 더 나 빠지며 -ve 값에 대한 결과는 정의되지 않습니다.) 따라서 서명되지 않은 모든 사물을 수행하는 것이 가장 좋습니다.

2의 보수를 위해, n 비트 ... a + ve 수는 비트 (n-1)에서부터 모두 '0'이어야하고 -ve 수는 모두 '1'이어야합니다. 따라서, C에서 (어떤 패딩!) 모든 부호없는 32 비트 정수를 가정 ...

m = UINT_MAX << (n - 1) ; // bits from n-1 upwards 
q = - (x >> 31) ;   // all sign bits, assuming 32bit integers 
return ((x^q) & m) == 0 ; 

나중에 추가

---

...

... 내가 작업하려고 투쟁하지 않았다 고백 당신의 코드 :

int fitsBits(int x, int n) 
    { 
    int mask = ~(1<<31); 
    return !(((x>>1)&mask)>>(~(~n+2)+1)); 
    } 

은 시도 중일 수 있습니다 (int 값을 이동하는 어려움이 있음). 그러나 mask 가정하면 0x7FFFFFFF로 끝나는, 그 (x>>1) 간단한 시프트 또는 후 산술 하나 하나이다 같이

• (x>>1)&mask 1의 단순 시프트이다 ((unsigned)x)>>1

• ~n+2~n+1+1 (우리는 2의 보수를 가정하기 때문에)

• 및 ~(~n+2)+1는 -(~n+2)가 -(-n+1)는 0123입니다입니다 -n+1입니다

• 그래서 (((x>>1)&mask)>>(~(~n+2)+1))는 (((unsigned)x)>>1)>>(n-1)은하기 위해 폐기 될 수있는 모든 비트 (드럼 롤) ...

  ... ((unsigned)x)>>n

...이다 n 비트 필드에 x을 저장하십시오.

하면 트릭을 할 것, x이 (((unsigned)x)>>n) == 0이 다음에, 부호n 비트 필드에 맞는 여부를 테스트하고자한다면.

이 가 가n 비트 필드에 서명로 x 맞는 서명 여부를 테스트하려면 x의 기호에 따라 제로 또는 0xFFFFFFFF>>(n-1)이어야합니다 ((unsigned)x)>>(n-1)의 가치에 대해 걱정할 필요.

(필자는이 요구 사항이 1<=n<=32 ... n=1 인 경우 부호 비트 만 갖기 때문에 -1..0이라는 숫자를 나타낼 수 있지만 특이하게 보이지만 그럼에도 불구하고 정확합니다.)