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

Question

Duplicar posible:
Best algorithm to count the number of set bits in a 32-bit integer?

¿Cómo contar el número de 1 's una serie tendrá en binario?

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

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

Lo que hace que esto sea 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 soporte, p. Intel/AMD

---

Para demostrar la eficacia de esta optimización es

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

impresiones

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

Cada número de bits utilizando la versión intrínseca y el bucle tarda sólo 0,4 nano-segundos en promedio. El uso de una copia del mismo código toma 6x más largo (obtiene el mismo resultado)

Answer 2

Consulte Bit Twidling Hacks y estudie todos los algoritmos 'conteo de bits establecidos'. 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 3

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

    return result; 
} 

Answer 4

La forma más eficaz para contar el número de 1 de en un 32-bits variable v que conozco 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. De acuerdo con Donald Knuth (The Art of Computer Programming Vol IV, p 11), el código apareció por primera vez en el primer libro de texto sobre programación, The Preparation of Programs for an Electronic Digital Computer por Wilkes, Wheeler y Gill (2da Edición 1957, reimpreso 1984). Páginas 191-193 de la 2da edición del libro presentado Nifty Parallel Count por D B Gillies y J C P Miller.

Answer 5

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

Answer 6

El más rápido que he usado y también visto en una implementación práctica (en la fuente abierta Sphinx Search Engine) es el MIT HAKMEM algorithm. Se ejecuta súper rápido en una gran cantidad de 1 y 0.

Answer 7

Lo siguiente es de la página "Bit Twiddling Hacks" o Knuth's books (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 8

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