suma - python while par o impar

Forma rápida de contar bits que no sean cero en un entero positivo

Question

Necesito una manera rápida de contar la cantidad de bits en un entero en Python. Mis soluciones actuales son

bin(n).count("1")

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

PD: (Represento una gran matriz binaria en 2D como una simple lista 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 extra.

Edición: 1. tiene que estar en python 2.7 o 2.6

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

por ejemplo, este es un caso de 2000 bits:

12448057941136394342297748548545082997815840357634948550739612798732309975923280685245876950055614362283769710705811182976142803324242407017104841062064840113262840137625582646683068904149296501029754654149991842951570880471230098259905004533869130509989042199261339990315125973721454059973605358766253998615919997174542922163484086066438120268185904663422979603026066685824578356173882166747093246377302371176167843247359636030248569148734824287739046916641832890744168385253915508446422276378715722482359321205673933317512861336054835392844676749610712462818600179225635467147870208L

Answer 1

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

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 .

Answer 2

De acuerdo con esta post , esta parece ser una de las implementaciones más rápidas del peso de Hamming (si no te importa usar unos 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 el range con xrange .

Editar

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

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

>>> import gmpy
>>> gmpy.popcount(2**1024-1)
1024

Answer 3

Dijiste que Numpy era demasiado lento. ¿Lo estabas usando para almacenar bits individuales? ¿Por qué no ampliar la idea de usar ints como matrices de bits, pero usar Numpy para almacenarlas?

Almacene n bits como una matriz de ceil(n/32.) entradas de 32 bits. A continuación, puede trabajar con la matriz numpy de la misma manera (bueno, lo suficientemente similar) que utiliza ints, incluido el uso de ellos para indexar otra matriz.

El algoritmo es básicamente calcular, en paralelo, la cantidad de bits configurados en cada celda, y sumar la cantidad de bits de cada celda.

setup = """
import numpy as np
#Using Paolo Moretti''s answer http://.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 estoy sorprendido, nadie sugirió que escribieras un módulo C.

Answer 4

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

Traté de adaptar las soluciones de Óscar y Adam para procesar el número entero en fragmentos de 64 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ó casi la mitad de tiempo).

Por otro lado, gmpy popcount() tardó aproximadamente popcount() el tiempo de bin(n).count("1") . Entonces, si puedes instalar gmpy, úsalo.

Answer 5

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

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

Answer 6

Puedes 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 extensible y el número de operaciones crece con el logaritmo del argumento (es decir, linealmente con el tamaño de bit del argumento).

Para entender cómo funciona, imagina que divides toda la cadena de 64 bits en 64 segmentos 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 han establecido los bits y 1 si se ha establecido un bit). La primera transformación da como resultado un estado análogo, pero con 32 cubos de 2 bits de longitud cada uno. Esto se logra desplazando los cubos de manera apropiada y agregando sus valores (una adición se ocupa de todos los segmentos, ya que no se puede llevar a través de los depósitos; el número de n bits siempre es lo suficientemente largo para codificar el número n). Transformaciones adicionales conducen a estados con una cantidad exponencialmente decreciente de cubos de tamaño exponencialmente creciente hasta que llegamos a un cubo de 64 bits de longitud. Esto proporciona la cantidad de bits configurados en el argumento original.

Answer 7

Resulta que su representación inicial es una lista de listas de entradas que son 1 o 0. Simplemente cuente 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 configurados, la manera 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; podría usar algún tipo de almacén de valores clave persistentes, o incluso MySql. (Otra opción sería implementar su propio almacenamiento simple basado en disco).