모집단 계산 알고리즘에 대한 약간의 설명을 던지십시오.

Question

나는 popcount (세트 비트의 수)를 수행하는 좋은 방법을 찾았습니다. 나는 몇 가지 예, 그것은 작동하는 진정한에 시도 여기

http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan

unsigned int v; // count the number of bits set in v 
unsigned int c; // c accumulates the total bits set in v 
for(c = 0; v; c++) 
{ 
    v &= v - 1; // clear the least significant bit set 
} 

이 하나를 발견했다. 이진 연산/표현의 어떤 속성이 작동하게합니까?

popcount 및 이진 표현에 대한 추가 정보가 있습니까?

Answer 1

초기에는 n 비트가 설정된 v으로 시작합니다.

게임의 요점은 루프의 반복마다 1 비트를 덜 계산하는 것입니다. 이렇게하면 처음 n의 값을 알아 내기 위해 n = 0 인 지점까지 루프의 반복 횟수를 계산할 수 있습니다.

n = 0이면 v = 0이므로 루프가이 지점에서 중지됩니다. 하지만 v> 0이면 루프의 본문을 적어도 한 번 실행합니다. 각각의 반복에서 우리는 1 비트 세트가 더 적은 v로 끝납니다.

여기 왜 있습니다. 첫 번째 속성은 v && v == v입니다. 이제 v은 비트 시퀀스 (정확한 비트 수는 컴퓨터/OS에 따라 다름)로, 가장 중요도가 가장 낮은 것부터 순서대로 정렬 할 수 있습니다. 1 0으로 설정됩니다에, 그 설정되어 [K] V를 호출,

1. 최하위 비트; 당신이 v을 감소 할 때, 우리는 다음을 참조 할 수 있습니다
2. v [k]보다 중요한 모든 비트는 v 일 때 이 아닌이 변경됩니다.

때문에, 그 감소량과 AND 연산 v은 V [K], 즉 V보다 덜 중요한 모든 비트 [K 0 및 정의가 모든 상위 비트 있지만 설정 V [K]를 유지한다 -1] ... v [0]는 v [k]가 "1 인 최하위 비트"이기 때문에 이미 0입니다. 따라서 ANDing 후 모든 하위 비트는 0으로 유지됩니다. 결과적으로 v && (v - 1)은 v보다 1로 설정된 1 비트가 더 적습니다. 0 비트로부터 비트를 감산 1

는

Answer 2

1로 그 비트를 회전뿐만 아니라 거기 빼기 1 결과 왼쪽에있는 다음 비트로부터 차용을 야기한다. 1 비트에 도달 할 때까지 왼쪽으로 계단식 연결을 계속합니다. 여기에서 1에서 1을 뺀 값은 0입니다. 이 시점에서 빼기가 완료됩니다. 0을 모두 1으로 첫 번째 세트 비트까지 변환하고 1에서 0으로 변환했습니다.

전후 값이 and 인 경우 before은 첫 번째 비트의 오른쪽에 0을 가지고 after은 그 비트에 0을 갖습니다. 0을 가진 anded는 0이므로, 원래의 값으로부터 모든 0을 유지하고 단일 비트도 0으로 설정합니다.