Necesito una manera rápida para contar el número de bits en un número entero en python.
Mi actual soluciones es

bin(n).count("1")

pero me pregunto si hay alguna forma más rápida de hacerlo?

PS: (estoy representando a una gran 2D matriz binaria como un único lista de números y haciendo operaciones a nivel de bit, y que trae el tiempo de horas a minutos. y ahora me gustaría deshacerse de esos minutos extra.

Editar:
1. tiene que ser en python 2.7 o 2.6

y optimización para números pequeños no importa mucho ya que no sería un claro cuello de botella, pero tengo los números con 10 000 + bits en algunos lugares

por ejemplo, esta es una de 2000 bits caso:

12448057941136394342297748548545082997815840357634948550739612798732309975923280685245876950055614362283769710705811182976142803324242407017104841062064840113262840137625582646683068904149296501029754654149991842951570880471230098259905004533869130509989042199261339990315125973721454059973605358766253998615919997174542922163484086066438120268185904663422979603026066685824578356173882166747093246377302371176167843247359636030248569148734824287739046916641832890744168385253915508446422276378715722482359321205673933317512861336054835392844676749610712462818600179225635467147870208L
  • Relacionados: stackoverflow.com/questions/407587/…
  • ¿Qué tipo de representación está utilizando si su «enteros» son más que un estándar de python int? ¿Que no tiene su propio método para el cálculo de este?
  • posibles duplicados de Número de bits de un número entero en Python
  • Para distinguir la cuestión de que en stackoverflow.com/a/2654211/1959808 (si es que está destinado a ser diferentes — al menos así parece) por favor, considere la posibilidad de reformular el título de «…contando el número de no-cero bits…» o similar. De lo contrario, int.bit_length debe ser la respuesta, y no la aceptó a continuación.
InformationsquelleAutor zidarsk8 | 2012-03-22

9 Comentarios

  1. 108

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

    Traté de adaptación Óscar y Adán soluciones para procesar el número entero de 64 bits y de 32 bits en trozos, respectivamente. Ambos fueron al menos diez veces más lento que bin(n).count("1") (la versión de 32 bits tomó alrededor de la mitad de mucho tiempo).

    Por otro lado, gmpy popcount() tomó cerca de 1/20 de la hora de bin(n).count("1"). Así que si usted puede instalar gmpy, el uso que.

    Para responder a una pregunta en los comentarios, para los bytes que haría uso de una tabla de búsqueda. Se puede generar en tiempo de ejecución:

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

    O simplemente definir 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 bits 1 en x donde 0 ≤ x ≤ 255.

    • +1! Lo contrario de esto no es exacto, sin embargo, debe ser indicado: bin(n).count("0") no es exacta debido a la ‘0b’ prefijo. Sería necesario bin(n)[2:].count('0') para aquellos contar naughts….
    • Realmente no se puede contar de cero bits sin saber cuántos bytes se está llenando, sin embargo, lo que es problemático con Python entero largo porque podría ser cualquier cosa.
    • Aunque esos son rápidos opciones para un solo números enteros, tenga en cuenta que los algoritmos presentados en otras respuestas pueden ser potencialmente vectorizada, por lo tanto mucho más rápido si se ejecuta a través de muchos de los elementos de una gran numpy matriz.
    • Para arrays de numpy me miraba con algo como esto: gist.github.com/aldro61/f604a3fa79b3dec5436a
    • He utilizado bin(n).count("1"). Sin embargo, sólo late entre 60% de python presentación. @ leetcode
    • «arbitrarias de longitud enteros» — Lo que si es que dado que la longitud es, decir, 8 bits?
    • Para 8 bits enteros que acababa de utilizar una tabla de búsqueda. Podría utilizar un objeto bytearray, para que el espacio de la eficiencia.

  2. 22

    Usted puede adaptar el algoritmo siguiente:

    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 64 bits en números positivos, pero es fácilmente extensible y el número de operaciones de crecimiento con el logaritmo de la argumentación (es decir, de forma lineal con el bit tamaño del argumento).

    Con el fin de entender cómo funciona esto de imaginar que se divide el entero de 64 bits de la cadena en 64 1-bit de los cubos. Cada segmento del valor es igual al número de bits en el cubo (0 si no hay bits se establecen y 1 si un bit está establecido). La primera transformación de los resultados en un análogo de estado, pero con 32 cubos cada 2 bits de largo. Esto se logra adecuadamente desplazamiento de los cubos y agregar sus valores (uno, además se encarga de todos los cubos ya que no llevan puede producirse a través de los cubos – n-número de bits es siempre el tiempo suficiente para codificar el número de n). Más transformaciones llevar a los estados con exponencialmente decreciente número de cubos de crecimiento exponencial de tamaño hasta llegar a uno de 64 bits de largo cubo. Esto da el número de bits en el argumento original.

    • Yo en serio no tengo idea de cómo esto funciona con 10 000 bits de números, pero me gusta la solución. me puedes dar una pista de si y cómo puedo applay que para números más grandes?
    • No veo el número de bits que estamos abordando aquí. Han considerado que la escritura de su manejo de los datos de código en un bajo nivel de un lenguaje como el C? Tal vez como una extensión de su código de python? Sin duda se puede mejorar el rendimiento mediante el uso de grandes matrices en C en comparación con las grandes números en python. Dicho esto, puede volver a escribir la CountBits() para manejar 10k-bits de los números mediante la adición de sólo 8 líneas de código. Pero va a ser difícil de manejar debido a la enorme constantes.
    • Puede escribir código para generar la secuencia de constantes, y establecer un lazo para el procesamiento.
    • Esta respuesta tiene la gran ventaja de que se puede vectorizada de los casos se trata de grandes numpy matrices.
  3. 13

    Aquí una implementación de Python de el recuento de la población del algoritmo, como se explica en este post:

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

    Va a trabajar para 0 <= i < 0x100000000.

    • Eso es inteligente. Busca esto en lugar de disparar una respuesta de la cadera es completamente adecuado!
    • Hizo referencia a esto? En mi máquina usando python 2.7, he encontrado esto para ser en realidad un poco más lento que bin(n).count("1").
    • No, yo no, podría usted por favor enviar sus puntos de referencia?
    • %timeit numberOfSetBits(23544235423): 1000000 loops, best of 3: 818 ns per loop; %timeit bitCountStr(23544235423): 1000000 loops, best of 3: 577 ns per loop.
    • Sin embargo, numberOfSetBits los procesos de mi 864×64 numpy.ndarray en 841 µs. Con bitCountStr tengo en bucle de forma explícita, y toma 40.7 ms, o casi 50 veces más.
  4. 8

    De acuerdo a este post, este parece ser uno de los más rápidos de la implementación de la Hamming de peso (si no te 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 reemplazar range con xrange.

    Editar

    Si usted necesita un mejor rendimiento (y sus números son grandes enteros), tener una mirada en el GMP de la biblioteca. Contiene escritos a mano asamblea implementaciones para diferentes arquitecturas.

    gmpy es Un C-codificado de extensión de Python módulo que contiene el GMP de la biblioteca.

    >>> import gmpy
    >>> gmpy.popcount(2**1024-1)
    1024
    • He editado mi pregunta para aclarar necesito esto para un Gran número (10k bits y más). la optimización de algo para 32 bits enteros sería probablt no hacer mucho de una diferencia, ya que el número de cuentas tendría que ser muy grande, en el que caso de que iba a causar la lentitud a la hora de ejecutarse.
    • Pero GMP es exactamente para números muy grandes, como los números y mucho más allá de los tamaños que usted menciona.
    • El uso de la memoria será mejor si usted usa array.array para POPCOUNT_TABLE16, como va a ser almacenados en un array de enteros, en lugar de como un dinámicamente el tamaño de la lista de Python int objetos.
  5. 3

    Me gusta mucho este método. Su sencillo y bastante rápido, pero también no se limita en la longitud de bits dado que python tiene una infinidad de números enteros.

    En realidad es más astuto de lo que parece, porque evita la pérdida de tiempo de escaneo de los ceros. Por ejemplo se tomará el mismo tiempo para contar el juego de bits de 1000000000000000000000010100000001 como en 1111.

    def get_bit_count(value):
       n = 0
       while value:
          n += 1
          value &= value-1
       return n
    • se ve muy bien, pero sólo es bueno para los muy «disperso» enteros. en promedio es bastante lento. Aún así, se ve muy útil en ciertos casos de uso.
    • No estoy muy seguro de lo que quieres decir con «en promedio es muy lento». Bastante lento en comparación con qué? A qué te refieres lento en comparación con algún otro código de python que no está citando? Es dos veces tan rápido como contando poco a poco por el promedio. De hecho, en mi macbook cuenta de 12,6 millones de bits por segundo, lo que es mucho más rápido que puedo contar con ellos. Si usted tiene un genérico de python algoritmo que funciona para cualquier longitud de número entero y es más rápido que este, me gustaría escuchar acerca de él.
    • Acepto que es realmente más lento que la respuesta de Manuel de arriba.
    • Bastante lento en promedio, significa, contando bits para 10000 números con 10000 dígitos toma 0.15 s con bin(n).count("1") pero tomó 3.8 s para su función. Si los números tenían muy pocos conjunto de bits que iba a funcionar rápido, pero si usted toma cualquier número al azar, en promedio, la función de arriba va a ser órdenes de magnitud más lento.
    • OK voy a aceptar eso. Supongo que solo quiero ser una polla cos eres un poco impreciso, pero que está totalmente a la derecha. Simplemente no las había probado el método que utiliza el método por Manuel antes de mi comentario. Se ve muy anticuado, pero es en realidad muy rápido. Ahora estoy utilizando una versión como eso, pero con 16 valores en el diccionario y que es incluso mucho más rápido que el que se ha citado. Pero para el registro que estaba usando en el mío en una aplicación con sólo un par de bits que se establecen en 1. Pero totalmente de bits aleatorios sí, se va a cerca de 50:50 con un poco de varianza disminuye con la longitud.
    • También gracias por tomar su tiempo para escribir y perfil de la función que he citado. Eso es apreciado.

  6. 2

    Usted dijo Numpy era demasiado lento. Se la estás utilizando para almacenar cada uno de los bits? ¿Por qué no extender la idea de utilizar enteros como matrices de bits pero el uso de Numpy para almacenar los?

    Store n de bits como una matriz de ceil(n/32.) de 32 bits enteros. Usted puede trabajar con la colección de la matriz de la misma (bueno, bastante similar) modo de usar enteros, incluyendo el uso de ellos para el índice de la otra matriz.

    El algoritmo es básicamente para calcular, en paralelo, el número de bits en cada celda, y a ellos se suma el bitcount 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 sugirió escribir un módulo C.

  7. 1

    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 los:

    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

    • Esto funciona rápido. Hay un error, al menos en p3, [1:] debe [2:] porque oct() devuelve ‘0o’ antes de la cadena. El código se ejecuta mucho más rápido, aunque si lo uso hex() en lugar de oct() y hacer un 16 entrada de diccionario,
  8. 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)
    
  9. -2

    Resulta de partida, la representación es una lista de listas de enteros que son 1 o 0. Simplemente contar en que la representación.


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

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

    Esto le proporcionará una constante de tiempo de búsqueda después de haber generado la lista. Ver a @PaoloMoretti la respuesta para una buena implementación de esta. Por supuesto, usted no tiene que mantener todo esto en la memoria – podría usar algún tipo de persistente clave-valor en el almacén, o incluso de MySql. (Otra opción sería la de poner en práctica sus propios simple almacenamiento basado en disco).

    • -0. Inteligente, pero ineficiente.
    • ¿Cómo es ineficiente?
    • Cuando leí tu respuesta contenía únicamente su primera frase: «El número de bits en un número entero es constante en python.»
    • Ya tengo un número de bits de la tabla de búsqueda para todos los de la cuenta que es posible almacenar, pero tener una gran lista de números y operar sobre ellos con un[i] & a[j] , hace que su soltuion inútil a menos que tenga más de 10 GB de ram. matriz para el & ^ | para tripples de 10000 números serían 3*10000^3 tamaño de la tabla de búsqueda. ya no sé lo que voy a necesitar, tiene más sentido solo en el conteo de los pocos miles cuando los necesito
    • O, se puede utilizar algún tipo de base de datos persistente o almacén de claves y valores.
    • 10+GB de ram no es increiblemente grande. Si desea realizar rápido computación numérica, no es razonable el uso de tamaño mediano-grande de hierro.
    • Lo siento, pero 10000^3 harían de este un 1000 000 000 000 números . si cada uno de ellos es el cálculo de 2000 bits que harían de este un 500+ horas de trabajo. Look up tables son buenas cuando se pueden utilizar, en este caso es imposible y no se la respuesta a mi pregunta. ps: por su método de trabajo que iba a necesitar una manera aún más rápida del recuento de estos bits.
    • también este algoritmo se tarda 3 minutos en mi leptop con 2 gb de ram (también de que 10G era optimista supongo), pero no vamos a discutir sobre esto, ya que claramente no tiene ninguna conexión con la pregunta original. Gracias de todos modos por intentarlo. Cada respuesta es una buena incluso si no es útil en este caso. (tal vez la próxima vez)
    • Sólo se necesita generar una tabla de una vez; de hecho, se puede generar tanto de forma incremental, y la pieza de comer, así que una vez que usted tiene una tabla de búsqueda que se completa a través de un determinado número de bits, usted puede tomar su entero en trozos de la longitud de bits, y el recuento de los bits en cada fragmento. Usted parece estar específicamente resisten a cualquier tipo de práctica de la solución propuesta en cualquier respuesta aquí. Por qué?
    • permítanos continuar esta discusión en el chat

Dejar respuesta

Please enter your comment!
Please enter your name here