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

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-битных микроконтроллерах. Тем не менее, он требует больше операций, чем большинство других решений. Сейчас я пытаюсь упростить это.

ОБНОВЛЕНИЕ2: @Evgeny Kluev предлагает другое решение, основанное на 64-битных регистрах

Answer 1

Я не уверен, что это то, что вы ищете, но вот только формула, использующая только сдвиги и побитовые и:

int weight(unsigned char x)
{
  return ((0x876543210 >>
    (((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)
}