Manera rápida de contar bits distintos de cero en un entero positivo

117

Necesito una forma rápida de contar la cantidad de bits en un número entero en Python. Mi solución actual es

bin(n).count("1")

pero me pregunto si hay alguna forma más rápida de hacer esto.

PD: (estoy representando una gran matriz binaria 2D como una lista única de números y haciendo operaciones bit a bit, y eso reduce el tiempo de horas a minutos. Y ahora me gustaría deshacerme de esos minutos adicionales.

Editar: 1. tiene que estar en Python 2.7 o 2.6

y optimizar para números pequeños no importa mucho, ya que eso no sería un cuello de botella claro, pero tengo números con más de 10000 bits en algunos lugares

por ejemplo, este es un caso de 2000 bits:

12448057941136394342297748548545082997815840357634948550739612798732309975923280685245876950055614362283769710705811182976142803324242407017104841062064840113262840137625582646683068904149296501029754654149991842951570880471230098259905004533869130509989042199261339990315125973721454059973605358766253998615919997174542922163484086066438120268185904663422979603026066685824578356173882166747093246377302371176167843247359636030248569148734824287739046916641832890744168385253915508446422276378715722482359321205673933317512861336054835392844676749610712462818600179225635467147870208L
zidarsk8
fuente
1
¿Qué tipo de representación estás usando si tus "números enteros" son más largos que un pitón estándar int? ¿No tiene su propio método para calcular esto?
Marcin
1
posible duplicado de Count bits de un entero en Python
endolith
3
Para distinguir la pregunta de la de stackoverflow.com/a/2654211/1959808 (si se pretende que sea diferente --- al menos así se ve), considere reformular el título como "... contando el número de cero bits ... ”o similar. De int.bit_lengthlo contrario, debería ser la respuesta, y no la aceptada a continuación.
Ioannis Filippidis

Respuestas:

121

Para enteros de longitud arbitraria, bin(n).count("1")es lo más rápido que pude encontrar en Python puro.

Intenté adaptar las soluciones de Óscar y Adam para procesar el entero en trozos de 64 bits y 32 bits, respectivamente. Ambos fueron al menos diez veces más lentos que bin(n).count("1")(la versión de 32 bits tomó aproximadamente la mitad de tiempo).

Por otro lado, gmpy popcount() tomó aproximadamente una vigésima parte del tiempo de bin(n).count("1"). Entonces, si puedes instalar gmpy, úsalo.

Para responder una pregunta en los comentarios, para bytes usaría una tabla de búsqueda. Puede generarlo en tiempo de ejecución:

counts = bytes(bin(x).count("1") for x in range(256))  # py2: use bytearray

O simplemente defínalo literalmente:

counts = (b'\x00\x01\x01\x02\x01\x02\x02\x03\x01\x02\x02\x03\x02\x03\x03\x04'
          b'\x01\x02\x02\x03\x02\x03\x03\x04\x02\x03\x03\x04\x03\x04\x04\x05'
          b'\x01\x02\x02\x03\x02\x03\x03\x04\x02\x03\x03\x04\x03\x04\x04\x05'
          b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'
          b'\x01\x02\x02\x03\x02\x03\x03\x04\x02\x03\x03\x04\x03\x04\x04\x05'
          b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'
          b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'
          b'\x03\x04\x04\x05\x04\x05\x05\x06\x04\x05\x05\x06\x05\x06\x06\x07'
          b'\x01\x02\x02\x03\x02\x03\x03\x04\x02\x03\x03\x04\x03\x04\x04\x05'
          b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'
          b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'
          b'\x03\x04\x04\x05\x04\x05\x05\x06\x04\x05\x05\x06\x05\x06\x06\x07'
          b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'
          b'\x03\x04\x04\x05\x04\x05\x05\x06\x04\x05\x05\x06\x05\x06\x06\x07'
          b'\x03\x04\x04\x05\x04\x05\x05\x06\x04\x05\x05\x06\x05\x06\x06\x07'
          b'\x04\x05\x05\x06\x05\x06\x06\x07\x05\x06\x06\x07\x06\x07\x07\x08')

Entonces es counts[x]para obtener el número de 1 bits en xdonde 0 ≤ x ≤ 255.

un poco
fuente
7
+1! Lo contrario de esto no es exacto, sin embargo, debe decirse: bin(n).count("0")no es exacto debido al prefijo '0b'. Tendría que ser bin(n)[2:].count('0')para aquellos que cuentan las travesuras ...
el lobo
11
Sin embargo, realmente no puede contar cero bits sin saber cuántos bytes está llenando, lo cual es problemático con un entero largo de Python porque podría ser cualquier cosa.
poco el
2
Aunque esas son opciones rápidas para enteros simples, tenga en cuenta que los algoritmos presentados en otras respuestas pueden potencialmente vectorizarse, por lo tanto, mucho más rápido si se ejecutan en muchos elementos de una numpymatriz grande .
gerrit
Para matrices numpy, buscaría algo como esto: gist.github.com/aldro61/f604a3fa79b3dec5436a
poco
1
He usado bin(n).count("1"). Sin embargo, solo supera el 60% de los envíos de Python. @ leetcode
northtree
29

Puede adaptar el siguiente algoritmo:

def CountBits(n):
  n = (n & 0x5555555555555555) + ((n & 0xAAAAAAAAAAAAAAAA) >> 1)
  n = (n & 0x3333333333333333) + ((n & 0xCCCCCCCCCCCCCCCC) >> 2)
  n = (n & 0x0F0F0F0F0F0F0F0F) + ((n & 0xF0F0F0F0F0F0F0F0) >> 4)
  n = (n & 0x00FF00FF00FF00FF) + ((n & 0xFF00FF00FF00FF00) >> 8)
  n = (n & 0x0000FFFF0000FFFF) + ((n & 0xFFFF0000FFFF0000) >> 16)
  n = (n & 0x00000000FFFFFFFF) + ((n & 0xFFFFFFFF00000000) >> 32) # This last & isn't strictly necessary.
  return n

Esto funciona para números positivos de 64 bits, pero es fácilmente ampliable y el número de operaciones crece con el logaritmo del argumento (es decir, linealmente con el tamaño de bits del argumento).

Para entender cómo funciona esto, imagine que divide toda la cadena de 64 bits en 64 depósitos de 1 bit. El valor de cada depósito es igual al número de bits establecidos en el depósito (0 si no se establecen bits y 1 si se establece un bit). La primera transformación da como resultado un estado análogo, pero con 32 cubos cada uno de 2 bits de longitud. Esto se logra cambiando apropiadamente los cubos y agregando sus valores (una adición se encarga de todos los cubos, ya que no puede ocurrir ningún acarreo entre cubos; el número de n bits siempre es lo suficientemente largo para codificar el número n). Las transformaciones adicionales conducen a estados con un número de cubos que disminuye exponencialmente y un tamaño que crece exponencialmente hasta que llegamos a un contenedor de 64 bits de longitud. Esto da el número de bits establecidos en el argumento original.

Adam Zalcman
fuente
En serio, no tengo idea de cómo funcionaría esto con números de 10000 bits, pero me gusta la solución. ¿Puede darme una pista si puedo aplicar eso a números más grandes y cómo puedo hacerlo?
zidarsk8
No vi la cantidad de bits con los que está tratando aquí. ¿Ha considerado escribir su código de manejo de datos en un lenguaje de bajo nivel como C? ¿Quizás como una extensión de su código de Python? Ciertamente, puede mejorar el rendimiento utilizando matrices grandes en C en comparación con números grandes en Python. Dicho esto, puede reescribir el CountBits()para manejar números de 10k bits agregando solo 8 líneas de código. Pero se volverá difícil de manejar debido a las enormes constantes.
Adam Zalcman
2
Puede escribir código para generar la secuencia de constantes y configurar un ciclo para el procesamiento.
Karl Knechtel
Esta respuesta tiene la gran ventaja de que se puede vectorizar para casos de numpyarreglos grandes .
gerrit
17

Aquí hay una implementación de Python del algoritmo de conteo de población, como se explica en esta publicación :

def numberOfSetBits(i):
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24

Funcionará para 0 <= i < 0x100000000.

Óscar López
fuente
Eso es inteligente. ¡Buscar esto en lugar de disparar una respuesta desde la cadera es completamente apropiado!
MrGomez
1
¿Lo comparaste? En mi máquina que usa Python 2.7, encontré que esto en realidad es un poco más lento que bin(n).count("1").
David Weldon
@DavidWeldon No, no lo hice, ¿podrían publicar sus puntos de referencia?
Óscar López
%timeit numberOfSetBits(23544235423): 1000000 loops, best of 3: 818 ns per loop; %timeit bitCountStr(23544235423): 1000000 loops, best of 3: 577 ns per loop.
gerrit
7
Sin embargo, numberOfSetBitsprocesa mis 864 × 64 numpy.ndarrayen 841 µs. Con bitCountStrtengo que hacer un bucle explícito, y tarda 40,7 ms, o casi 50 veces más.
gerrit
8

Según esta publicación , esta parece ser una de las implementaciones más rápidas del peso Hamming (si no le importa usar alrededor de 64 KB de memoria).

#http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetTable
POPCOUNT_TABLE16 = [0] * 2**16
for index in range(len(POPCOUNT_TABLE16)):
    POPCOUNT_TABLE16[index] = (index & 1) + POPCOUNT_TABLE16[index >> 1]

def popcount32_table16(v):
    return (POPCOUNT_TABLE16[ v        & 0xffff] +
            POPCOUNT_TABLE16[(v >> 16) & 0xffff])

En Python 2.x debe reemplazarlo rangecon xrange.

Editar

Si necesita un mejor rendimiento (y sus números son enteros grandes), eche un vistazo a la GMPbiblioteca. Contiene implementaciones de ensamblaje escritas a mano para muchas arquitecturas diferentes.

gmpy es un módulo de extensión de Python codificado en C que envuelve la biblioteca GMP.

>>> import gmpy
>>> gmpy.popcount(2**1024-1)
1024
Paolo Moretti
fuente
He editado mi pregunta para dejar en claro que lo necesito para números grandes (10k bits y más). optimizar algo para enteros de 32 bits probablemente no supondría una gran diferencia, ya que el número de recuentos tendría que ser realmente grande, en cuyo caso eso provocaría un tiempo de ejecución lento.
zidarsk8
Pero GMP es exactamente para números muy grandes, incluidos números en y mucho más allá de los tamaños que menciona.
James Youngman
1
El uso de la memoria será mejor si usa array.arrayfor POPCOUNT_TABLE16, ya que entonces se almacenará como una matriz de números enteros, en lugar de como una lista de intobjetos Python de tamaño dinámico .
gsnedders
6

Me gusta mucho este método. Es simple y bastante rápido, pero tampoco está limitado en la longitud de bits, ya que Python tiene números enteros infinitos.

En realidad, es más astuto de lo que parece, porque evita perder el tiempo escaneando los ceros. Por ejemplo, tomará el mismo tiempo contar los bits establecidos en 1000000000000000000000010100000001 que en 1111.

def get_bit_count(value):
   n = 0
   while value:
      n += 1
      value &= value-1
   return n
Robotbugs
fuente
se ve muy bien, pero solo es bueno para números enteros muy "escasos". en promedio es bastante lento. Aún así, parece realmente útil en ciertos casos de uso.
zidarsk8
No estoy muy seguro de lo que quiere decir con "en promedio, es bastante lento". ¿Bastante lento comparado con qué? ¿Te refieres a lento en comparación con algún otro código de Python que no estás citando? Es dos veces más rápido que contar poco a poco el número promedio. De hecho, en mi macbook cuenta 12,6 millones de bits por segundo, que es mucho más rápido de lo que puedo contarlos. Si tiene otro algoritmo de Python genérico que funcione para cualquier longitud de entero y sea más rápido que este, me gustaría saberlo.
Robotbugs
1
Acepto que en realidad es más lento que la respuesta de Manuel anterior.
Robotbugs
Bastante lento en promedio significa, contar bits para 10000 números con 10000 dígitos toma 0.15s con bin(n).count("1")pero tomó 3.8s para tu función. Si los números tuvieran muy pocos bits, funcionaría rápido, pero si toma cualquier número aleatorio, en promedio, la función anterior será órdenes de magnitud más lenta.
zidarsk8
OK, lo aceptaré. Supongo que solo estaba siendo un idiota porque eres un poco impreciso, pero tienes toda la razón. Simplemente no había probado el método con el método de Manuel anterior antes de mi comentario. Parece muy torpe pero en realidad es muy rápido. Ahora estoy usando una versión así pero con 16 valores en el diccionario y eso es incluso mucho más rápido que el que citó. Pero para que conste, estaba usando el mío en una aplicación con solo unos pocos bits que se establecieron en 1. Pero para bits totalmente aleatorios, sí, va a aproximadamente 50:50 con una pequeña variación que disminuye con la longitud.
Robotbugs
3

Puede utilizar el algoritmo para obtener la cadena binaria [1] de un entero, pero en lugar de concatenar la cadena, contando el número de unos:

def count_ones(a):
    s = 0
    t = {'0':0, '1':1, '2':1, '3':2, '4':1, '5':2, '6':2, '7':3}
    for c in oct(a)[1:]:
        s += t[c]
    return s

[1] https://wiki.python.org/moin/BitManipulation

Manuel
fuente
Esto funciona rápido. Hay un error, al menos en p3, el [1:] debería ser [2:] porque oct () devuelve '0o' antes de la cadena. El código se ejecuta mucho más rápido, aunque si se utiliza hexagonal () en lugar de OCT () y hacer un diccionario de entrada 16,
Robotbugs
2

Dijiste que Numpy era demasiado lento. ¿Lo estaba utilizando para almacenar bits individuales? ¿Por qué no extender la idea de usar ints como matrices de bits pero usar Numpy para almacenarlos?

Almacene n bits como una matriz de entradas de ceil(n/32.)32 bits. Luego puede trabajar con la matriz numpy de la misma manera (bueno, lo suficientemente similar) en la que usa ints, incluido su uso para indexar otra matriz.

El algoritmo consiste básicamente en calcular, en paralelo, el número de bits establecidos en cada celda, y suman el recuento de bits de cada celda.

setup = """
import numpy as np
#Using Paolo Moretti's answer http://stackoverflow.com/a/9829855/2963903
POPCOUNT_TABLE16 = np.zeros(2**16, dtype=int) #has to be an array

for index in range(len(POPCOUNT_TABLE16)):
    POPCOUNT_TABLE16[index] = (index & 1) + POPCOUNT_TABLE16[index >> 1]

def popcount32_table16(v):
    return (POPCOUNT_TABLE16[ v        & 0xffff] +
            POPCOUNT_TABLE16[(v >> 16) & 0xffff])

def count1s(v):
    return popcount32_table16(v).sum()

v1 = np.arange(1000)*1234567                       #numpy array
v2 = sum(int(x)<<(32*i) for i, x in enumerate(v1)) #single int
"""
from timeit import timeit

timeit("count1s(v1)", setup=setup)        #49.55184188873349
timeit("bin(v2).count('1')", setup=setup) #225.1857464598633

Aunque me sorprende que nadie te sugiera que escribas un módulo C.

leewz
fuente
0
#Python prg to count set bits
#Function to count set bits
def bin(n):
    count=0
    while(n>=1):
        if(n%2==0):
            n=n//2
        else:
            count+=1
            n=n//2
    print("Count of set bits:",count)
#Fetch the input from user
num=int(input("Enter number: "))
#Output
bin(num)
Praveen Narala
fuente
-2

Resulta que su representación inicial es una lista de listas de entradas que son 1 o 0. Simplemente cuéntelas en esa representación.


El número de bits en un entero es constante en Python.

Sin embargo, si desea contar el número de bits establecidos, la forma más rápida es crear una lista que se ajuste al siguiente pseudocódigo: [numberofsetbits(n) for n in range(MAXINT)]

Esto le proporcionará una búsqueda de tiempo constante después de haber generado la lista. Vea la respuesta de @ PaoloMoretti para una buena implementación de esto. Por supuesto, no es necesario que guarde todo esto en la memoria; puede usar algún tipo de almacén de valores clave persistente o incluso MySql. (Otra opción sería implementar su propio almacenamiento simple basado en disco).

Marcin
fuente
@StevenRumbalski ¿Cómo es inútil?
Marcin
Cuando leí su respuesta, solo contenía su primera oración: "El número de bits en un entero es constante en Python".
Steven Rumbalski
Ya tengo una tabla de búsqueda de recuentos de bits para todos los recuentos que es posible almacenar, pero tener una lista grande de números y operar con ellos con una [i] y una [j], hace que su solución sea inútil a menos que tenga más de 10 GB de RAM. matriz para & ^ | para triples de 10000 números sería 3 * 10000 ^ 3 tamaño de tabla de búsqueda. ya que no sé lo que necesitaré, tiene más sentido contar los pocos miles cuando los necesito
zidarsk8
@ zidarsk8 O bien, podría usar algún tipo de base de datos o almacén de valores clave persistente.
Marcin
@ zidarsk8 10 + GB de RAM no es sorprendentemente grande. Si desea realizar un cálculo numérico rápido, no es descabellado utilizar hierro mediano-grande.
Marcin