C#에서 UInt32의 설정 비트를 계산하는 가장 빠른 방법은 무엇입니까

Question

조회 테이블을 사용하지 않고 UInt32에서 설정 비트 수를 계산하는 가장 빠른 방법은 무엇입니까? 즉, 1의 수를 계산하는 가장 빠른 방법은 무엇입니까? O (1)에서 셀 수있는 방법이 있습니까?

Answer 1

bit-twiddling hacks 페이지에는 다양한 옵션이 있습니다. 32 개 개의 모든 가능한 비트를 반복하는 것은 O (N)가이 같은 비용 매번 편의상 :

있다는 것을 물론

, 당신은, 내가 생각 하는데요 주장 할 수 룩업 테이블-행된 바이트 방식, 또는 나뿐만 써서 설정 비트가있는만큼, 반복 처리 브라이언 커니 핸의 깔끔한 아이디어 :

public static int CountBits(uint value) 
{ 
    int count = 0; 
    while (value != 0) 
    { 
     count++; 
     value &= value - 1; 
    } 
    return count; 
} 

당신이 256 항목의 조회 테이블을 채우기의 아이디어를 좋아하지 않는 경우를, nybble 조회는 여전히 꽤 빠를 것입니다. 8 개의 배열 조회가 32 간단한 비트 연산보다 느릴 수도 있습니다.

물론 난해한 접근법을 사용하기 전에 앱의 실제 성능을 테스트 해 볼 가치가 있습니다. 이것이 정말로 병목 현상입니까?

Answer 2

은의 중복 : how-to-implement-bitcount-using-only-bitwise-operators 또는 best-algorithm-to-count-the-number-of-set-bits-in-a-32-bit-integer

그리고 그 문제에 대한 많은 솔루션이 있습니다. 내가 사용하는 하나입니다 : [이 게시물] (의 대답에

int NumberOfSetBits(int i) 
    { 
     i = i - ((i >> 1) & 0x55555555); 
     i = (i & 0x33333333) + ((i >> 2) & 0x33333333); 
     return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24; 
    }