Вес Хэмминга написан только в бинарных операциях?

Question

Мне нужно написать выражение одного байтового веса Хэмминга только по бинарным операциям (&, ^, >>); без какой-либо петли, просто формулы.

Я знаю, что существует множество алгоритмов, которые позволяют вычислять вес Хэмминга, но все они используют арифметические операции или цикл.

Если мы возьмем алгоритм из 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 Клюева

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). Вот код (в Go) для pop-count 32-битного целого числа. Расширение этого до 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) 
}