количество единиц в 32-битном числе

Question

Я ищу способ иметь число 1 в 32-битном числе без использования петли между ними. может ли любое тело помочь мне и предоставить мне код или алгоритм сделать это. Заранее спасибо.

Answer 1

См. Integer.bitCount(int). Вы можете обратиться к исходному коду, если хотите увидеть, как он работает; многие из подпрограмм класса битов Integer взяты из Восхищение Хакера.

Answer 2

См. Канонический справочник: Битовые хаки Twiddling

Answer 3

Короткий, непристойно оптимизированный ответ (на С):

int pop(unsigned x) {
   x = x - ((x >> 1) & 0x55555555);
   x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
   x = (x + (x >> 4)) & 0x0F0F0F0F;
   x = x + (x >> 8);
   x = x + (x >> 16);
   return x & 0x0000003F;
}

Чтобы понять, почему эта магия работает, см. Поиски ускоренного подсчета населения Генри С. Уорреном-младшим, глава 10 в Красивый код .

Answer 4

Мой личный фаворит, прямо из Bit Twiddling Hacks :

v = v - ((v >> 1) & 0x55555555);
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;

Answer 5

Вы можете определить это рекурсивно:

int bitcount(int x) {
  return (x==0) ? 0 : (x & 1 + bitcount(x/2));
}

Приведенный выше код не тестируется и, вероятно, работает только при x> = 0. Надеюсь, вы все равно поймете идею ...

Answer 6

Разделить 32-битное число на четыре 8-битных числа (см. Оператор сдвига битов, приведение и т. Д.)

Затем используйте поиск с 256 записями, который преобразует 8-битное число в установленное количество битов. Добавьте четыре результата, presto!

Кроме того, посмотрите, что сказал Митч Уит - немного поиграть, может быть очень весело;)

Answer 7

Ниже приводится реализация Integer.bitCount в JDK 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;
}