Число 1 в 32-битном номере

Ответ 1

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

Ответ 2

См. каноническую ссылку: Бит Twiddling Hacks

Ответ 3

Короткий, неприлично оптимизированный ответ (в C):

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 в "Красивом коде".

Ответ 4

Разделите 32-битное число на четыре 8-битных числа (см. оператор смещения бит, кастинг и т.д.)

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

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

Ответ 5

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

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

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

Ответ 6

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

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

Ответ 7

Ниже приведена реализация JDK 1.5 Integer.bitCount

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;
}