java - sistema - ¿Cómo contar la cantidad de 1 que tendrá un número en binario?

sistema binario ejercicios

Question

Posible duplicado:
¿El mejor algoritmo para contar la cantidad de bits configurados en un entero de 32 bits?

¿Cómo cuento el número de 1 tendrá un número en binario?

Entonces digamos que tengo el número 45 , que es igual a 101101 en binario y tiene 4 1 ''s en él. ¿Cuál es la forma más eficiente de escribir un algoritmo para hacer esto?

Answer 1

El más rápido que he usado y también visto en una implementación práctica (en el motor de búsqueda de código abierto Sphinx ) es el algoritmo MIT HAKMEM . Se ejecuta súper rápido en una gran cantidad de 1 y 0.

Answer 2

El siguiente código de Ruby funciona para números positivos.

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

Answer 3

En lugar de escribir un algoritmo para hacer esto, es mejor usar la función incorporada. Integer.bitCount()

Lo que lo hace especialmente eficiente es que la JVM puede tratar esto como algo intrínseco. es decir, reconocer y reemplazar todo con una sola instrucción de código de máquina en una plataforma que lo admita, por ejemplo, Intel / AMD

Para demostrar cuán efectiva es esta optimización

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

huellas dactilares

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

Cada bit cuenta usando la versión intrínseca y el bucle toma solo 0.4 nanosegundos en promedio. Usar una copia del mismo código tarda 6 veces más (obtiene el mismo resultado)

Answer 4

Esto se llama peso de Hamming . También se llama population count , population count popcount o sideways sum .

Answer 5

La manera más eficiente de contar el número de 1 en una variable de 32 bits v yo sé es:

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

Actualizado: Quiero dejar en claro que no es mi código, en realidad es más viejo que yo. Según Donald Knuth ( El arte de la programación de computadoras Vol IV, p 11), el código apareció por primera vez en el primer libro de texto sobre programación, La preparación de programas para una computadora digital electrónica de Wilkes, Wheeler y Gill (2nd Ed 1957, reimpreso 1984 ) Las páginas 191-193 de la segunda edición del libro presentaron Nifty Parallel Count de DB Gillies y JCP Miller.

Answer 6

Lo siguiente es de la página "Bit Twyddling Hacks" o de los libros de Knuth (no lo recuerdo). Está adaptado a enteros sin signo de 64 bits y funciona en C #. No sé si la falta de valores sin firmar en Java crea un problema.

Por cierto, escribo el código solo para referencia; la mejor respuesta es usar Integer.bitCount() como dijo @Lawrey; ya que hay una operación específica de código de máquina para esta operación en algunas (pero no todas) las CPU.

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

Answer 7

Vea Bit Twidling Hacks y estudie todos los algoritmos ''counting bits set''. En particular, el camino de Brian Kernighan es simple y bastante rápido si esperas una respuesta pequeña. Si espera una respuesta distribuida uniformemente, la tabla de búsqueda podría ser mejor.

Answer 8

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

    return result;
}