Как подсчитать число 1, которое число будет иметь в двоичном формате?

Ответ 1

Вместо написания алгоритма для этого лучше всего использовать встроенную функцию. Integer.bitCount()

Что делает это особенно эффективным, так это то, что JVM может рассматривать это как внутреннее. то есть распознавать и заменять все это единичной машинной кодовой инструкцией на платформе, которая поддерживает ее, например. Intel/AMD

Чтобы продемонстрировать, насколько эффективна эта оптимизация

public static void main(String... args) {
    perfTestIntrinsic();

    perfTestACopy();
}

private static void perfTestIntrinsic() {
    long start = System.nanoTime();
    long countBits = 0;
    for (int i = 0; i < Integer.MAX_VALUE; i++)
        countBits += Integer.bitCount(i);
    long time = System.nanoTime() - start;
    System.out.printf("Intrinsic: Each bit count took %.1f ns, countBits=%d%n", (double) time / Integer.MAX_VALUE, countBits);
}

private static void perfTestACopy() {
    long start2 = System.nanoTime();
    long countBits2 = 0;
    for (int i = 0; i < Integer.MAX_VALUE; i++)
        countBits2 += myBitCount(i);
    long time2 = System.nanoTime() - start2;
    System.out.printf("Copy of same code: Each bit count took %.1f ns, countBits=%d%n", (double) time2 / Integer.MAX_VALUE, countBits2);
}

// Copied from Integer.bitCount()
public static int myBitCount(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;
}

печатает

Intrinsic: Each bit count took 0.4 ns, countBits=33285996513
Copy of same code: Each bit count took 2.4 ns, countBits=33285996513

Каждое количество бит с использованием встроенной версии и цикла занимает в среднем всего 0,4 нано-секунды. Использование копии того же кода занимает 6 раз (получает тот же результат)

Ответ 2

Самый эффективный способ подсчета числа 1 в 32-битной переменной v Я знаю:

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

Обновлено: Я хочу пояснить, что это не мой код, на самом деле он старше меня. Согласно Дональд Кнут (Искусство компьютерного программирования Vol IV, p 11), код впервые появился в первом учебнике по программированию, Подготовка программ для электронного цифрового компьютера Wilkes, Wheeler and Gill (2-е изд 1957, переиздано в 1984 году). Страницы 191-193 второго издания книги представлены Nifty Parallel Count by D B Gillies и J C P Miller.

Ответ 3

Смотрите Bit Twidling Hacks и изучите все алгоритмы набора счетных бит. В частности, способ Брайана Кернигана прост и довольно быстр, если вы ожидаете небольшого ответа. Если вы ожидаете равномерно распределенного ответа, таблица поиска может быть лучше.

Ответ 4

Это называется вес Хэмминга. Он также называется population count, popcount или sideways sum.

Ответ 5

Ниже приведена страница "Бит Tweedling Hacks" или "Книги Кнута" (я не помню). Он адаптирован для неподписанных 64-битных целых чисел и работает на С#. Я не знаю, создает ли проблема отсутствие неподписанных значений в Java.

Кстати, я пишу код только для справки; лучший ответ - использовать Integer.bitCount(), как сказал @Lawrey; поскольку в некоторых (но не во всех) ЦП существует определенная операция машинного кода для этой операции.

  const UInt64 m1 = 0x5555555555555555;
  const UInt64 m2 = 0x3333333333333333;
  const UInt64 m4 = 0x0f0f0f0f0f0f0f0f;
  const UInt64 h01 = 0x0101010101010101;

  public int Count(UInt64 x)
  {
      x -= (x >> 1) & m1;
      x = (x & m2) + ((x >> 2) & m2);
      x = (x + (x >> 4)) & m4;
      return (int) ((x * h01) >> 56);
  }

Ответ 6

public int f(int n) 
{
    int result = 0;
    for(;n > 0; n = n >> 1)
        result += ((n & 1) == 1 ? 1 : 0);

    return result;
}

Ответ 7

Самый быстрый, который я использовал, а также видел в практической реализации (в open source Sphinx Search Engine) является алгоритм MIT HAKMEM. Он работает сверхбыстрый по очень большому потоку 1 и 0.

Ответ 8

Следующий код Ruby работает для положительных чисел.

count = 0
while num > 1
    count = (num % 2 == 1) ? count + 1 : count
    num = num >> 1
end
count += 1
return count