32 비트 부호없는 정수의 역 비트

Question

32 비트 부호없는 정수의 비트를 반전하는 것은 Java에 사용되는 부호없는 정수가 아니기 때문에 발생합니다.

내 코드에는 두 가지 버전이 있습니다. 나는이 문제가 :

(1) 제 1 차 및 2 차 솔루션 (올바른지) 같은 값을 반환하지 않는 이유

(2) 제 1 차 및 2 차 솔루션이 올바른을받지 잘못 어디로 갔는지 그러나 정답을 반환

//reverse(3) return 4294967296 
    public static long reverse(long a) { 
     long numBits = 32L; 
     long finalResult = 0L; 
     for(long i = 0L; i < numBits; i++){ 
      long ithBit = a & (1L << i); 
      finalResult = finalResult + ithBit * (1L << (numBits - i - 1L)); 
     } 
     return finalResult; 
    } 

이 코드 (솔루션) :

//reverse(3) returns 0 
    public static long reverse(long a) { 
     long numBits = 32; 
     long finalResult = 0; 
     for(int i = 0; i < numBits; i++){ 
      long ithBit = a & (1 << i); 
      finalResult = finalResult + ithBit * (1 << (numBits - i - 1)); 
     } 
     return finalResult; 
    } 

두 번째 버전에 대답

//reverse(3) returns 3221225472 
    public static long reverse(long A) { 
     long rev = 0; 

     for (int i = 0; i < 32; i++) { 
      rev <<= 1; 
      if ((A & (1 << i)) != 0) 
       rev |= 1; 
     } 

     return rev; 

    } 

감사! 두 숫자 비트 (31)의 동일한 비트 패턴에 곱 때문에

ithBit * (1 << (numBits - i - 1)); 

가 (32)가 설정되고 : 두 버전의

Answer 1

당신은 여기에 논리 문제가 있습니다. 만약 int을 비트 시프트하고 있기 때문에 비트 0가 설정된 경우 버전 1에서

는 첨가량 그래서 비트 시프트 결과 격에 대한 상위 비트가 설정되는 것으로 -2^31를 나타낸다 int 또는 2^31이다 -2^31이고 비트는 결과의 오랜 기간 동안 자동 캐스트가 가능하기 때문에 가능합니다. 각 종류의 두 비트 (0 및 비 0)가 있으므로 결과는 0입니다.

버전 2에는 동일한 문제가 있지만 비트가 long이기 때문에 음수가 아닌 int 문제가 없습니다. 각 비트가 1이면 2^31이 추가됩니다. 숫자 3에는 2 비트가 설정되어 있으므로 2 * 2^31 (또는 2^32)은 4294967296입니다.

---

논리를 수정하려면 버전 2를 사용하고 곱셈을 ithBit으로 제거하십시오.

Answer 2

반복 할 때마다 값을 살펴 보겠습니다. 설명을 위해, 우리는 중간 값을 살펴해야합니다, 그래서 우리가 코드를 변경할 수 있습니다 :

이

int n = (1 << (numBits - i - 1)); 
long m = ithBit * n; 
finalResult = finalResult + m; 

귀하의 시작 값이 3 :

a = 0000 0000 0000 0000 0000 0000 0000 0011 

첫 번째 루프 반복 (I = 0) :

ithBit  = 00000000 00000000 00000000 00000001 
n   = 11111111 11111111 11111111 11111111 10000000 00000000 00000000 00000000 
m   = 11111111 11111111 11111111 11111111 10000000 00000000 00000000 00000000 
finalResult = 11111111 11111111 11111111 11111111 10000000 00000000 00000000 00000000 

2 루프 반복 (I = 1)

ithBit  = 00000000 00000000 00000000 00000010 
n   = 01000000 00000000 00000000 00000000 
m   = 10000000 00000000 00000000 00000000 
finalResult = 00000000 00000000 00000000 00000000 

첫 번째 반복은 n = 1 << 31 인 -2147483648을 설정합니다. 두 번째 버전에서는 n = 1L << 31 (2147483648)을 사용하므로 두 버전의 결과가 다릅니다.

도 알 수 있듯이 은 부분에 m = ithBit * n 부분을 쓰고 싶지 않습니다.

직접 인쇄하여 전화 번호를 확인하면 알아낼 수 있습니다.

현재 여기 내 버전입니다. 이해하는데 어려움이있는 경우 중간 값을 인쇄하여 현재 진행중인 작업을 확인하십시오.

public static long reverse4(long a) { 
    long rev = 0; 
    for (int i = 0; i < 32; i++, a >>= 1) 
     rev = (rev << 1) | (a & 1); 
    return rev; 
} 

Answer 3

"i 번째 비트"가 0이나 1이 아니라 오히려 가려져있는 것이 두 가지 예입니다. 두 경우 모두 31 번째 비트는 0x8000_0000입니다. 첫 번째 경우 int는 int이므로 음수이고 long으로 변환하면 음수입니다. 두 번째 경우에는 이미 길기 때문에 긍정적 인 상태를 유지합니다. 당신이 의도하지, 그래서 그것을 해결하기 위해 수행

ithBit = (a >>> i) & 1; 

그런데, long이 바보 사용; 서명되지 않은 서명과 서명 된 서명은 Java에서 두 가지 유형의 교대가 있다는 것을 이해하는 한 큰 차이가 없습니다.

그런데 세 가지 예 모두 끔찍합니다. 비트 조작을한다면 속도를 원하니? (왜 다른 비트 귀찮게?)

이 오른쪽 (http://graphics.stanford.edu/~seander/bithacks.html#ReverseByteWith32Bits에서 도난하지 광산)을 수행하는 방법이다 : 우리가 오랫동안 사용하는 부호없는 정수가없는 자바 이후

a = ((a >>> 1) & 0x55555555) | ((a & 0x55555555) << 1); 
a = ((a >>> 2) & 0x33333333) | ((a & 0x33333333) << 2); 
a = ((a >>> 4) & 0x0F0F0F0F) | ((a & 0x0F0F0F0F) << 4); 
a = ((a >>> 8) & 0x00FF00FF) | ((a & 0x00FF00FF) << 8); 
a = (a >>> 16   ) | (a    << 16); 

Answer 4

합니다. 통상의 불필요한

자바 사용 two's complement representation에 서명하고 서명 된 숫자에 대해 동일한 비트 패턴의 분열과 비교 결과를 제외하고 모든 연산입니다. 후자의 경우에는 Integer.divideUnsigned(int, int)과 Integer.compareUnsigned(int, int)을 사용할 수 있습니다.

문제는 그들이 것이 좋습니다 읽는 시간을 보내고, Integer.reverse(int)

Relevant docs있어 32 비트 부호없는 정수

의 비트를 반전하는 것입니다.