Bitwise - bitCount의 수식 의미?

여기에 Integer.bitCount (int i)의 코드 복사본이 있습니다.Bitwise - bitCount의 수식 의미?

나는 모든 연산자를 이해하지만 그 마법 수를 알아낼 수있는 방법을 모르겠습니다! 아무도 나에게 그걸 설명 할 수 있니? 패턴 (1,2,4,8,16 & 0x5,0x3,0x0f)을 볼 수 있습니다.

 public static int bitCount(int i) { 
      // HD, Figure 5-2 
      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; 
     }

출처

2014-10-01 Jaxox

가능한 복제본 [복잡한 c 코드, 어떻게 작동하는지 설명하는 데 필요한 사람이 있습니까?] (http://stackoverflow.com/questions/14841995/complex-c-code-i-need-any-one- - 어떻게 - 어떻게 - 어떻게 - - - 작품 -) –

@ PaulR 당신은 실제로 다른 게시물을 읽었습니까? 실제로 수식/알고리즘을 설명하는 곳은 어디입니까? 플러스 다른 게시물은 C와 다른 수식 너무! 그게 어떻게 중복 될 수 있습니까? – Jaxox

답변은 [여기] (http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel)에 링크되어 있으며 여기 및 기타 병렬 비트 계산 방법을 설명합니다. Java와 C 기반 언어의 더 넓은 계열은 모두 동일하거나 유사한 비트 연산자와 구문을 공유하기 때문에 언어는 거의 무의미합니다. 또한이 질문에는 다른 많은 중복이 있음을 유의하십시오. 하나만 골라내는 것이 어려웠고, 가장 좋은 것을 선택하지 않았을 수도 있습니다. 또한 여기에 아주 좋은 대답이 있습니다 : http://stackoverflow.com/a/109025/253056 –

OK, 당신의 코드는 32 개 비트 정수입니다 만, 알파벳 32 개 글자를 가지고 있지 않기 때문에의 16 비트에 대한 첫 번째 단계를 알아낼 수 있습니다. 입력 내용의 이진 형태를 가정 (공백으로 나타낸 바이트 경계) 그래서 제 할당의 우측의 제 2 비트 (AB - 0A)이다

i     = ABCDEFGH IJKLMNOP 
i >>> 1   = 0ABCDEFG HIJKLMNO 
(i >>> 1) & 0x5555 = 0A0C0E0G 0I0K0M0O

이다. 조합을 시도해보십시오

A B AB-0A 
0 0 00-00 = 00 
1 0 10-01 = 01 
0 1 01-00 = 01 
1 1 11-01 = 10

그래서 그 결과의 처음 두 비트는 입력의 처음 두 비트 당신에게 비트의 수을 제공합니다. 두 비트의 다른 모든 그룹에도 동일하게 적용됩니다.

이제 다시 똑같은 일을하십시오. 이번에는 기본 4의 입력을 고려할 것이므로 두 비트는 아래 표기의 숫자를 형성하며 전체 32 비트를 사용할 수 있습니다.

i      = ABCD EFGH IJKL MNOP 
i & 0x33333333   = 0B0D 0F0H 0J0L 0N0P 
i >>> 2    = 0ABC DEFG HIJK LMNO 
(i >>> 2) & 0x33333333 = 0A0C 0E0G 0I0K 0M0O

그래서 결과의 제 4 비트 (0A + 0B) = A + B, 그리고 동일한 4 개 비트를 임의의 다른 그룹에 대해 유지한다. 따라서이 시점에서 4 비트의 모든 그룹은 원래 입력에서이 4 비트의 비트 수를 포함합니다. 베이스 (16)를 사용

, 다음 단계는 각 4 비트 그룹의 비트 수는 항상 4 비트로 표현 될 수있는 두 개의 이러한 카운트를 추가 네 미만 때문 작동

i       = AB CD EF GH 
i >>> 4      = 0A BC DE FG 
i + (i >>> 4)    = A(A+B) (B+C)(C+D) (D+E)(E+F) (F+G)(G+H) 
(i + (i >>> 4)) & 0x0f0f0f0f = 0(A+B) 0(C+D) 0(E+F) 0(G+H)

인 오버플로없이. 따라서 덧셈은 하나의 4 비트 16 진수에서 다른 16 진수로 오버 플로우되지 않습니다. 이 시점에서 입력의 해당 바이트에 대한 비트 수를 포함하는 각 바이트가 있습니다. Other algorithms 거기에서 똑똑한 곱셈을 사용하여 contin 수 있지만 인용 된 코드를 다음 단계뿐만 아니라 추가 스틱.

i       = A B C D 
i >>> 8      = 0 A B C 
i2 = i + (i >>> 8)   = A (A+B) (B+C) (C+D) 
i2 >>> 16     = 0 0 A (A+B) 
i3 = i2 + (i2 >>> 1   = A (A+B) (A+B+C) (A+B+C+D) 
i3 & 0x3f     = 0 0 0 (A+B+C+D)

또 다시 숫자 사이에 오버플로가 없음을 사용합니다.

출처

2014-10-02 09:50:08 MvG

Bitwise - bitCount의 수식 의미?

답변

관련 문제