Java에서이 비트 조작은 어떻게 작동합니까?

Question

자바가 int의 비트 수를 계산하는 방법을 조사하고있었습니다.
나는이 같은 간단한 내 마음에 뭔가를했다 (내가 생각하는 올바른) :

public static int bitCount(int number){ 
     final int MASK = 0x1; 
     int count = 0; 

     for(int i = 0; i < 32; i++){ 
      if(((number >>> i) & MASK) == MASK){ 
       count++; 
      } 
     } 
     return count; 
    } 

가 대신 내가 절대적으로 무엇을하는지 아무 생각하는 방법을 발견 (나에게 마법처럼 보인다) :

i = i - ((i >>> 1) & 0x55555555); 
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333); 
i = (i + (i >>> 4)) & 0x0f0f0f0f; 
i = i + (i >>> 8); 
i = i + (i >>> 16); 
return i & 0x3f; 

누군가가이 기능이 무엇인지 이해하고 왜 내가 처음 생각한 것과 같은 단순한 기능이 나쁜지 이해할 수 있습니까?

Answer 1

물론

i = i - ((i >>> 1) & 0x55555555); 

5 비트 패턴 0101 (4 비트)이기 때문에, 마스크 비트 패턴 01 여섯 차례의 반복이다. 이 행은 숫자의 2 비트 쌍마다 비트 수를 계산합니다. 2 비트 쌍을 고려하면 (i >>> 1) & 0x1은 하위 순서로 상위 비트를 가져옵니다. 이제, 4 가지 가능한 2 비트 패턴이 있습니다.

00 ~> 00 - 00 = 00 
01 ~> 01 - 00 = 01 
10 ~> 10 - 01 = 01 
11 ~> 11 - 01 = 10 

각 2 비트 쌍에는 원본이 해당 위치에 있었던 비트 수가 포함됩니다.

i = (i & 0x33333333) + ((i >>> 2) & 0x33333333); 

다음으로 각 4 비트 그룹 (일명 니블)에있는 비트를 계산합니다. 0x3 = 0011(b)으로 니블을 마스킹함으로써 니블의 하위 2 비트에있는 비트 수를 얻고 (i >>> 2) & 0x3은 니블의 상위 2 비트에서 카운트를 얻습니다. 이 카운트가 추가되었습니다. 각 개수가 최대 2이기 때문에 합계는 최대 4 개이므로 니블을 남기지 않습니다.

i = (i + (i >>> 4)) & 0x0f0f0f0f; 

이제 각 옥텟의 비트가 계산됩니다. 각 니블은 그 위치에서 원본에 설정된 비트 수를 포함합니다. 오른쪽으로 4 비트 이동하면 각 위치의 상위 니블에서 하위 니블로 카운트가 이동합니다. 그런 다음 우리는 또한 하위 오름차순 니블에서 인접 옥 테트의 상위 오벌 냅으로 카운트를 옮겼습니다. 그 값은 & 0x0f0f0f0f으로 마스크 처리되었습니다. 각 옥텟은 최대 8 비트가 설정 될 수 있기 때문에 카운트는 옥텟의 하위 니블을 떠나지 않습니다.

i = i + (i >>> 8); 

이제 인접 옥텟 쌍의 수를 추가합니다.

i = i + (i >>> 16); 

이제 우리는 상위 2 옥텟과 하위 2의 카운트 합계를 추가합니다.높은 순서 옥텟은 여전히 ​​중간 수를 포함하기 때문에

return i & 0x3f; 

마지막으로, 가장 낮은 순서 옥텟을 제외한 모든 옥텟은 마스크 아웃된다.

간단한 구현이 나쁜 것으로 간주 될 수있는 이유는 성능 때문입니다. 복잡한 비트 해킹은 더 적은 연산과 분기를 사용하므로 더 빠릅니다. 그러나 잘못 될 가능성은 훨씬 더 큽니다.

int (또는 long)에서 설정 한 비트를 계산하는 또 다른 깔끔한 방법은 n = n & (n-1)이 n의 마지막 세트 비트를 해제하고 훼손되지 않은 다른 모든 잎 때문에 작동

public static int bitCount(int n) { 
    int count = 0; 
    while(n != 0) { 
     ++count; 
     n = n & (n-1); 
    } 
    return count; 
} 

입니다. n의 비트 패턴

...100...0 

로 끝나면 n-1의 비트 패턴

...011...1 

이고 n의 마지막 1 비트 전의 비트가 동일하다. Java에서는 integer overflow가 wrap-around 의미론을 가지고 있기 때문에 음수에 대해서도 작동합니다. 따라서 n = Integer.MIN_VALUE 인 경우 비트 패턴은 100...0이고 n - 1은 이되고 비트 패턴은 011...1입니다.

Answer 2

멋진 방법은 컴퓨터에 int 값의 유한 범위가 있기 때문에 작동합니다. 계산 전에 필요한 모든 마스크를 알아야하기 때문에 BigInteger와 같이 무한 범위에서 쉽게 작동하지 않습니다 (다른 멋진 비트 알고리즘). http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

는이 장 하단에 : 그것은을 통해 어떻게 작동하는지 어떤 경우에

, 당신은 읽을 수 있습니다.