Простой и быстрый способ рассчитать расстояние Хемминга двоичного целого числа до 0?

Question

Простой и быстрый способ рассчитать расстояние Хемминга двоичного целого числа до 0?

Я пишу решатель судоку, и я должен рассчитать то, что я узнал, называется расстоянием Хэмминга int в 0например, расстояние Хэмминга 7 (111 в двоичном виде) в 0 является 3, Так что я просто делаю:

for(int dist = 0 ; num != 0 ; num>>=1) dist += (num&1);

Хотя это работает хорошо, я нахожу это немного неуклюжим. Я пытался придумать трюк с бинарной операцией для вычисления расстояния (в основном для развлечения), но я мог найти способ, который работает только на расстоянии 1:

(num-1) ^ ((num<<1)-1) == num → true only if hamming dist to 0 == 1

Я посмотрел на StackOverflow и в сети, но ничего не смог найти.

При условии, что num является никогда отрицательный и всегда меньше, чем 512Есть ли более приятный / более элегантный способ оценить его, возможно, некоторые приемы бинарных операций? Если нет, учитывая приведенные выше предположения, существует ли приближение расстояния Хэмминга, которое всегда будет в пределах ошибки < 1?

2

binary-operators c++hamming-distance java

Решение

Другие решения

Чтобы создать справочную таблицу для 9 бит (поскольку это для Судоку):

int dist[512];
dist[0] = 0;
for (i=1; i<512; i++)
dist[i] = (i&1) + dist[i/2];

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

int dist(int bits) {
static _dist[512] = {};
if (bits == 0)
return 0;
else if (_dist[bits] == 0)
_dist[bits] = (bits & 1) + dist(bits/2);
return _dist[bits];

2

Не уверен, если это поможет, но из любопытства я реализовал это с помощью шаблонов:

template <int N>
struct Hamming {
enum { value = Hamming< (N/2) >::value + (N&1)};
};
template <>
struct Hamming<0>
{
enum { value = 0 };
};int main() {
std::cout << Hamming<7>::value << std::endl;
return 0;
}

Его можно использовать, только если N известно во время компиляции, поэтому я думаю, что вам придется использовать что-то еще в вашем случае. Однако это наглядно демонстрирует, как можно (в принципе) избежать любых вычислений во время выполнения.

0

Источник

Accepted Answer

В Java вы можете использовать статический метод Integer.bitCount (int i)

Если вам это нужно на другом языке, это Java-источник, который должен быть довольно простым для перевода.

/**
* Returns the number of one-bits in the two's complement binary
* representation of the specified {@code int} value.  This function is
* sometimes referred to as the <i>population count</i>.
*
* @param i the value whose bits are to be counted
* @return the number of one-bits in the two's complement binary
*     representation of the specified {@code int} value.
* @since 1.5
*/
public static int bitCount(int i) {
// HD, Figure 5-2
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}

1