이 코드는 어떻게 1 비트 수를 계산합니까?

Question

주어진 정수의 이진 표현에서 1-bits의 수를 세는 다음 코드를 찾았습니다. 아무도 어떻게 작동하는지 설명 할 수 있습니까? 그런 작업을 위해 비트 마스크를 어떻게 선택합니까? 감사.

int count_one(int x) 
{ 
    x = (x & (0x55555555)) + ((x >> 1) & (0x55555555)); 
    x = (x & (0x33333333)) + ((x >> 2) & (0x33333333)); 
    x = (x & (0x0f0f0f0f)) + ((x >> 4) & (0x0f0f0f0f)); 
    x = (x & (0x00ff00ff)) + ((x >> 8) & (0x00ff00ff)); 
    x = (x & (0x0000ffff)) + ((x >> 16) & (0x0000ffff)); 
    return x; 
} 

Answer 1

이 알고리즘은 계산 소스와 메모리 모두로 x을 사용합니다. 첫째, 비트 마스크가 무엇인지에 대해 생각 :

0x55 = 01010101 
0x33 = 00110011 
0x0f = 00001111 
0xff = 11111111 

이의는 8 비트 예제로 가자 : 우리는이 두 가지를 추가 할 경우는 01,101,010

a & 0x55 = 01000000; (a >> 1) & 0x55 = 00010101 

, 우리는 각 두 비트의 비트 수를 얻을 = 쌍. 이 결과는 마스크가 각 추가에 대해 단 하나의 비트 세트를 갖기 때문에 많아야 0x10입니다.

이제 우리는 0x33 마스크를 사용합니다. 각 연속 2 비트는 첫 번째 연산의 결과를 포함하고 있습니다. 이 마스크를 사용하여 연속 4 비트를 마스크하여 추가합니다. 이 결과는 최대로 0x100입니다. x의 결과가 나올 때까지 다른 마스크와 계속됩니다.

종이로 시험해보십시오. 몇 단계를 거치면 매우 명확 해집니다.

Answer 2

설명하기 쉽게하기 위해, 정수가 4 비트이고 각 비트가 1,2,3,4로 표시된다고 가정 해 봅시다. 1-bits의 번호를 얻으려면 먼저 1과 2의 합계와 3과 4의 합계를 구한 다음이 합계를 더할 수 있습니다.

x & (0x5) 1 없애고 3, x & (0xa) 2를 제거하는 것이며, 제 x & (0x5) + (x & (0xa) >> 1) 1의 합을 저장하는 1 2 비트를 사용하고 (2) 및 (3)의 합을 저장하는 3 4 비트를 사용하여 제 x & (0x5) + (x & (0xa) >> 1)는 동일한 것 x & (0x5) + (x >> 1) & (0x5)입니다.

이제 우리는 합계 1과 2를 모두 x에 저장했습니다. 결과를 더할 수 있습니다. 상기와 동일하게, x & (0x3)은 3의 합계를 얻을 것이며, x & (0x12)은 1의 합을 얻습니다. x & (0x3) + (x & (0x12)) >> 2은 최종 결과를 얻을 것입니다. x & (0x3) + (x & (0x12)) >> 2은 x & (0x3) + (x >> 2) & (0x3)과 동일합니다.

내부에서 일어나는 일을 볼 수 있습니다. 귀하의 경우, 첫 번째 라인은 1 2 3 4 5 6의 합계를 얻을 수 있습니다. 그리고 두 번째 줄에서는 1 2 3 4와 5 6 7 8의 합을 얻습니다. 그래서 이것을 5 번하면 모든 32 비트의 수를 얻을 수 있습니다.

Answer 3

이것은 분단하고 정복하는 접근 방식입니다. 첫 번째 줄은 후속 쌍에 대한 합계를, 그 다음에 이어지는 네 쌍에 대한 합계, 그리고 마지막으로 비트 수를 제공합니다.

예 우리는 심지어 비트 하나에 의해 이동 홀수 비트 &을 주먹 라인에서

1011001111000110 

을 (16 비트 그래서 마지막 줄없이 코드를 고려). 그런 다음 추가합니다.홀수 비트에 대한

num: 10 11 00 11 11 00 01 10 
mask: 01 01 01 01 01 01 01 01 
res: 00 01 00 01 01 00 01 00 

: 심지어 비트를 들어

num>>1: 01 01 10 01 11 10 00 11 
mask: 01 01 01 01 01 01 01 01 
res: 01 01 00 01 01 00 00 01 

우리는 다음과 같은 마스크와 우리는 같은 반복 이후 쌍

01 10 00 10 10 00 01 01 

의 총액을 그 결과를 추가 취득 및 대응하는 교대

,

2nd: 0011 0011 0011 0011 
3rd: 0000 1111 0000 1111 
4th: 0000 0000 1111 1111 

그리고 얻을 :

2nd: 0011 0010 0010 0010 // 3 set in the first four, 2 in other quadrupels 
3rd: 0000 0101 0000 0100 // 5 bits set in the first eight, 4 in the rest 
4th: 0000 0000 0000 1001 // 9 bits in total 

Answer 4

첫번째 라인 16 2 비트 정수 배열, 표현의 결과로서 정수 처리 0 2 비트 쌍 0 비트가 설정 되었다면 2 비트 쌍의 1 비트가 설정된 경우 (1 빈 또는 10 빈), 2 비트 쌍의 두 비트가 모두 설정된 경우 2입니다. 이는 두 개의 비트 중 낮은 쪽이 x이고 두 비트 중 낮은 쪽이 x이라고 생각하기 때문입니다. 그들을 함께 추가하십시오. 당사의 summands는 0 또는 1로 제한되기 때문에 2 비트 쌍 외부에서 carry가 발생하지 않습니다. 결과는 x에 다시 저장됩니다.

x = (x & (0x55555555)) + ((x >> 1) & (0x55555555));

다음 라인은 모든 4 비트를 차지하는데 사용되는 두 피가수에 그 합을 기억 똑같은 별도 정수마다 2 비트들을 처리 시간이, 않는다. 이 연산 후에 정수는 근본적으로 8 개의 4 비트 정수로 이루어진 배열이됩니다. 연산 전에 각 summand는 마지막 행의 계수에 해당하므로 0, 1 또는 2 (10 진수)입니다. 이 때문에 우리는 각 합계가 4보다 크지 않다는 것을 안다. 각 4 비트 int는 최대 값 15 (10 진수)를 가지므로 오버플로가 발생하지 않는다는 것을 알고있다. 위와 같이 결과는 x에 다시 저장됩니다.

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

우리는 전술 한 바와 같이 8 비트의 각 세트에 4 비트의 모든 쌍을 suming 이번에 똑같이.

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

우리는 그 다음 16 비트 (x의 상부 및 하부 절반)의 각 쌍의 8 비트들의 어느 쌍 합계.

x = (x & (0x00ff00ff)) + ((x >> 8) & (0x00ff00ff));

는 이제 x의 상부 및 하부 절반을 합산하고, 우리는 x의 값에 설정된 비트 수에 해당하는 32 비트 값으로 남겨진다. 여기

x = (x & (0x0000ffff)) + ((x >> 16) & (0x0000ffff));

키 우리는 32 비트 정수 그 자체의 총 비트 수로 남을 때까지의 각 단계의 비트 인플레 이스 페어 수가 없다는 것이다.