숫자로 비트를 계산합니다 [복제

StackOverflow https://stackoverflow.com/questions/843737

문제

복제하다:

32 비트 정수에서 세트 비트 수를 계산하는 최상의 알고리즘?

숫자가 있다고 가정 해 봅시다. 반복을 사용하지 않고 해당 숫자의 이진 표현에서 1에 해당하는 비트를 계산할 수있는 방법이 있습니까? 내 말은, 약간의 연산자와 마스크를 사용하여 일정한 시간에 할 수있는 방법이 있습니까? 두 아키텍처 모두 32 비트와 64 비트에 잘 작동하는 솔루션이 필요합니다. 아 거의 잊어 버렸습니다. C 언어 나 어셈블러에도 필요합니다.

도움이 되었습니까?

해결책

루프가없는 약간 계산 알고리즘이 있습니다. http://graphics.stanford.edu/~sander/bithacks.html. 많은 비트 계산 알고리즘 http://gurmeetsingh.wordpress.com/2008/08/05/fast-bit-counting-routines/

다른 팁

물론, 당신은 그것을 좋아하지 않을 것입니다.

물론 모든 올바른 값이있는 조회 테이블을 만들 수 있습니다.

표 [1] = 1, 표 [2] = 1, 표 [3] = 2 등

그래서 이것은 당신에게 줄 것입니다 정말 빠릅니다 답변이지만 테이블이 매우 크고 크기 때문에 완전히 쓸모없는 해결책입니다.

이것을 조금 최적화 할 수 있지만 약간의 반복이 필요합니다. 8 비트 버전의 테이블 솔루션 인 256 개 엔트리 테이블을 만듭니다. 그런 다음 점검 할 값의 각 바이트를 반복하여 테이블 조회 결과를 요약하십시오. 같은 것 :

short int tableLookup[256] = { 0, 1, 1, 2, 1, ... };
unsigned int valueToCheck = 89392491;
int result = 0;
while ( valueToCheck != 0 ) {
   result += tableLookup[ (valueToCheck & 0xFF) ];
   valueToCheck >>= 8;
}
// result should now have the correct bit count, if the table is correct.

흠, 이것은 잘 알려진 것 같습니다 (그리고 여기서 나는 내 머리 꼭대기에서 이것을하고있었습니다) :http://graphics.stanford.edu/~seander/bithacks.html#countbitsnaive

예, a를 사용하여 할 수 있습니다 테이블을 찾으십시오.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top