해밍 웨이트는 바이너리 연산으로 만 쓰여졌습니까?

Question

바이너리 연산만으로 1 바이트 해밍 웨이트의 표현식을 작성해야합니다 (&, ^, >>); 어떤 고리도없이 그냥 수식.

나는 해밍 무게를 계산할 수있는 많은 알고리즘이 있지만, 모두 산술 연산이나 루핑을 사용한다는 것을 알고있다.

우리 http://en.wikipedia.org/wiki/Hamming_weight에서 알고리즘 후 제 합 D = B + C가 D = B^C^(B & C < < 1)로 작성하지만, 다음 두 합이 더 복잡 할 수 걸리는 경우.

힌트가 있습니까?

업데이트 : 도움 주셔서 감사합니다.

int popcount_1(unsigned char in){ 

unsigned char m1 = 0x55; 
unsigned char m2 = 0x33; 
unsigned char m4 = 0x0f; 
unsigned char B,C = 0; 
unsigned char x = in; 

x = (x & (x << 1) & (m1 << 1)) | (m1 & (x^(x >> 1))); 

B = x & m2; 
C = (x >> 2) & m2; 
x = B^C^((B & C) << 1); 

B = (x & m4)^((x >> 4) & m4); 
C = (x & ((x >> 4) & m4)) << 1; 
x = B^C^((B & C) << 1); 
return x; 
} 

이 코드는에 변수 의 무게를 해밍가 발생합니다 : 사실, 나는 다음과 같은 무언가를 필요로했다. +, - 또는 비교 명령어가 포함되어 있지 않으며 8 비트 마이크로 컨트롤러에서 작동 할 수 있습니다. 그러나 대부분의 다른 솔루션보다 많은 작업이 필요합니다. 이제, 나는 그것을 단순화하려고 노력하고있다.

UPDATE2 : 또 다른 해결책, 64 개 비트 레지스터를 기반으로, @Evgeny Kluev에 의해 제안

Answer 1

이 당신이 검색 것입니다, 그러나 여기에만 변화와 비트 등을 사용하여 단지 공식 경우 잘 모르겠어요 :

int weight(unsigned char x) 
{ 
    return ((0x>> 
    (((0x4332322132212110 >> ((x & 0xF) << 2)) & 0xF) << 2)) >> 
    ((0x4332322132212110 >> (((x & 0xF0) >> 2)) & 0xF) << 2)) 
    & 0xf; 
} 

여기서 시프트 연산은 배열 인덱싱 (4 비트 해밍 가중치를 찾기) 대신에 두 번 사용됩니다. 그리고 하나 더 많은 시프트 연산은 배열 인덱싱을 사용하여 더하기를 수행합니다.

Answer 2

내가 할 수있는 최선의 방법은 O (log n)입니다. 다음은 32 비트 정수의 pop-count에 대한 코드입니다 (Go에서). 이를 64 비트로 확장하면 분명히 실제로 어떤 일이 벌어지고 있는지 명확히 알 수 있습니다.

func popCount(n uint32) int { 
    // each bit in n is a one-bit integer that indicates how many bits are set 
    // in that bit. 

    n = ((n & 0xAAAAAAAA) >> 1) + (n & 0x55555555) 
    // Now every two bits are a two bit integer that indicate how many bits were 
    // set in those two bits in the original number 

    n = ((n & 0xCCCCCCCC) >> 2) + (n & 0x33333333) 
    // Now we're at 4 bits 

    n = ((n & 0xF0F0F0F0) >> 4) + (n & 0x0F0F0F0F) 
    // 8 bits 

    n = ((n & 0xFF00FF00) >> 8) + (n & 0x00FF00FF) 
    // 16 bits 

    n = ((n & 0xFFFF0000) >> 16) + (n & 0x0000FFFF) 
    // kaboom - 32 bits 

    return int(n) 
}