Maneira rápida de contar bits diferentes de zero em número inteiro positivo

117

Preciso de uma maneira rápida de contar o número de bits em um número inteiro em python. Minha solução atual é

bin(n).count("1")

mas estou me perguntando se existe alguma maneira mais rápida de fazer isso?

PS: (estou representando uma grande matriz binária 2D como uma única lista de números e fazendo operações bit a bit, o que reduz o tempo de horas para minutos. Agora, gostaria de me livrar desses minutos extras.

Editar: 1. tem que estar em python 2.7 ou 2.6

e otimizar para pequenos números não importa muito, pois isso não seria um gargalo claro, mas eu tenho números com mais de 10.000 bits em alguns lugares

por exemplo, este é um caso de 2.000 bits:

12448057941136394342297748548545082997815840357634948550739612798732309975923280685245876950055614362283769710705811182976142803324242407017104841062064840113262840137625582646683068904149296501029754654149991842951570880471230098259905004533869130509989042199261339990315125973721454059973605358766253998615919997174542922163484086066438120268185904663422979603026066685824578356173882166747093246377302371176167843247359636030248569148734824287739046916641832890744168385253915508446422276378715722482359321205673933317512861336054835392844676749610712462818600179225635467147870208L
zidarsk8
fonte
1
Que tipo de representação você está usando se seus "inteiros" forem mais longos do que um python padrão int? Isso não tem seu próprio método para calcular isso?
Marcin
1
possível duplicata de bits Count de um inteiro em Python
endolith de
3
Para distinguir a pergunta daquela em stackoverflow.com/a/2654211/1959808 (se a intenção for diferente --- pelo menos assim parece), considere reformular o título para “... contando o número de não zero bits ... ”ou similar. Caso contrário, int.bit_lengthdeve ser a resposta, e não a aceita abaixo.
Ioannis Filippidis

Respostas:

121

Para inteiros de comprimento arbitrário, bin(n).count("1")é o mais rápido que encontrei no Python puro.

Tentei adaptar as soluções de Óscar e Adam para processar o inteiro em blocos de 64 bits e 32 bits, respectivamente. Ambos foram pelo menos dez vezes mais lentos do que bin(n).count("1")(a versão de 32 bits levou cerca de metade do tempo novamente).

Por outro lado, o gmpy popcount() demorou cerca de 1/20 do tempo de bin(n).count("1"). Então, se você pode instalar o gmpy, use-o.

Para responder a uma pergunta nos comentários, para bytes eu usaria uma tabela de pesquisa. Você pode gerá-lo em tempo de execução:

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

Ou apenas defina 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')

Então, é counts[x]para obter o número de 1 bits em xque 0 ≤ x ≤ 255.

kindall
fonte
7
+1! O inverso disso não é preciso, no entanto, deve ser declarado: bin(n).count("0")não é preciso por causa do prefixo '0b'. Precisaria ser bin(n)[2:].count('0')para aqueles contando nada ....
o lobo
11
Você não pode realmente contar zero bits sem saber quantos bytes está enchendo, o que é problemático com um inteiro longo do Python porque pode ser qualquer coisa.
kindall
2
Embora essas sejam opções rápidas para números inteiros únicos, observe que os algoritmos apresentados em outras respostas podem ser potencialmente vetorizados, portanto, muito mais rápidos se executados em muitos elementos de uma grande numpymatriz.
gerrit
Para matrizes numpy, eu procuraria algo assim: gist.github.com/aldro61/f604a3fa79b3dec5436a
kindall
1
Eu usei bin(n).count("1"). No entanto, supera apenas 60% do envio de python. @ leetcode
northtree
29

Você pode adaptar o seguinte 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

Isso funciona para números positivos de 64 bits, mas é facilmente extensível e o número de operações aumenta com o logaritmo do argumento (ou seja, linearmente com o tamanho de bits do argumento).

Para entender como isso funciona, imagine que você divida toda a string de 64 bits em 64 intervalos de 1 bit. O valor de cada depósito é igual ao número de bits definido no depósito (0 se nenhum bit for definido e 1 se um bit for definido). A primeira transformação resulta em um estado análogo, mas com 32 intervalos de 2 bits cada. Isso é conseguido deslocando apropriadamente os depósitos e adicionando seus valores (uma adição cuida de todos os depósitos, uma vez que nenhum transporte pode ocorrer entre os depósitos - o número de n bits é sempre longo o suficiente para codificar o número n). Outras transformações levam a estados com número exponencialmente decrescente de intervalos de tamanho crescente até chegarmos a um longo intervalo de 64 bits. Isso dá o número de bits definido no argumento original.

Adam Zalcman
fonte
Sinceramente, não tenho ideia de como isso funcionaria com números de 10.000 bits, mas gosto da solução. você pode me dar uma dica se e como posso aplicar isso a números maiores?
zidarsk8,
Não vi o número de bits com que você está lidando aqui. Você já pensou em escrever seu código de tratamento de dados em uma linguagem de baixo nível como C? Talvez como uma extensão do seu código python? Você certamente pode melhorar o desempenho usando grandes matrizes em C em comparação com grandes números em python. Dito isso, você pode reescrever o CountBits()para lidar com números de 10k bits adicionando apenas 8 linhas de código. Mas se tornará difícil devido a constantes enormes.
Adam Zalcman
2
Você pode escrever código para gerar a sequência de constantes e configurar um loop para o processamento.
Karl Knechtel
Essa resposta tem a grande vantagem de poder ser vetorizada para casos que lidam com grandes numpyarrays.
gerrit
17

Esta é uma implementação em Python do algoritmo de contagem de população, conforme explicado nesta postagem :

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

Vai funcionar para 0 <= i < 0x100000000.

Óscar López
fonte
Isso é inteligente. Olhar para cima em vez de dar uma resposta pelo quadril é completamente apropriado!
Mr Gomez,
1
Você comparou isso? Na minha máquina usando o python 2.7, descobri que isso realmente é um pouco mais lento do que bin(n).count("1").
David Weldon,
@DavidWeldon Não, não, você poderia postar seus benchmarks?
Ó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
No entanto, numberOfSetBitsprocessa meu 864 × 64 numpy.ndarrayem 841 µs. Com bitCountStreu tenho que fazer um loop explicitamente, e leva 40,7 ms, ou quase 50 vezes mais.
gerrit
8

De acordo com esta postagem , esta parece ser uma das implementações mais rápidas do peso Hamming (se você não se importar em usar cerca de 64 KB de memória).

#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])

No Python 2.x você deve substituir rangepor xrange.

Editar

Se você precisa de melhor desempenho (e seus números são inteiros grandes), dê uma olhada na GMPbiblioteca. Ele contém implementações de montagem escritas à mão para muitas arquiteturas diferentes.

gmpy é um módulo de extensão Python codificado em C que envolve a biblioteca GMP.

>>> import gmpy
>>> gmpy.popcount(2**1024-1)
1024
Paolo Moretti
fonte
Editei minha pergunta para deixar claro que preciso disso para números grandes (10k bits e mais). otimizar algo para inteiros de 32 bits provavelmente não faria muita diferença, já que o número de contagens teria que ser muito grande, caso em que isso causaria o tempo de execução lento.
zidarsk8,
Mas GMP é exatamente para números muito grandes, incluindo números em e muito além dos tamanhos que você mencionou.
James Youngman
1
O uso da memória será melhor se você usar array.arraypara POPCOUNT_TABLE16, já que será armazenado como um array de inteiros, em vez de uma lista de intobjetos Python de tamanho dinâmico .
gsnedders
6

Eu realmente gosto desse método. É simples e muito rápido, mas também não é limitado no comprimento de bits, pois o python tem números inteiros infinitos.

Na verdade, é mais astuto do que parece, porque evita perder tempo digitalizando os zeros. Por exemplo, levará o mesmo tempo para contar os bits definidos em 1000000000000000000000010100000001 como em 1111.

def get_bit_count(value):
   n = 0
   while value:
      n += 1
      value &= value-1
   return n
Robotbugs
fonte
parece ótimo, mas só é bom para inteiros muito "esparsos". em média, é bastante lento. Ainda assim, parece muito útil em certos casos de uso.
zidarsk8
Não tenho certeza do que você quer dizer com "em média é muito lento". Muito lento em comparação com o quê? Você quer dizer lento em comparação com algum outro código python que você não está citando? É duas vezes mais rápido do que contar bit a bit para o número médio. Na verdade, no meu macbook ele conta 12,6 milhões de bits por segundo, o que é muito mais rápido do que eu consigo contá-los. Se você tiver outro algoritmo python genérico que funciona para qualquer comprimento de inteiro e é mais rápido do que isso, gostaria de saber mais sobre ele.
Robotbugs
1
Aceito que na verdade é mais lento do que a resposta do Manuel acima.
Robotbugs
Muito lento, em média, significa que a contagem de bits para 10.000 números com 10.000 dígitos leva 0,15s com, bin(n).count("1")mas demorou 3,8s para sua função. Se os números tivessem poucos bits definidos, funcionaria rápido, mas se você pegar qualquer número aleatório, em média, a função acima será ordens de magnitude mais lenta.
zidarsk8
OK, vou aceitar isso. Acho que só estava sendo um idiota porque você é um pouco impreciso, mas está totalmente certo. Só não tinha testado o método usando o método de Manuel acima antes do meu comentário. Parece muito desajeitado, mas na verdade é muito rápido. Agora estou usando uma versão assim, mas com 16 valores no dicionário e que é ainda muito mais rápida do que a que ele citou. Mas, para o registro, eu estava usando o meu em um aplicativo com apenas alguns bits definidos como 1. Mas para bits totalmente aleatórios, sim, vai para cerca de 50:50 com uma pequena variação diminuindo com o comprimento.
Robotbugs
3

Você pode usar o algoritmo para obter a string binária [1] de um inteiro, mas em vez de concatenar a string, contando o 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

Manuel
fonte
Isso funciona rápido. Há um erro, pelo menos em p3, o [1:] deveria ser [2:] porque oct () retorna '0o' antes da string. O código roda muito mais rápido se você usar hex () em vez de oct () e criar um dicionário de 16 entradas,
Robotbugs
2

Você disse que Numpy era muito lento. Você o estava usando para armazenar bits individuais? Por que não estender a ideia de usar ints como arrays de bits, mas usar o Numpy para armazená-los?

Armazene n bits como uma matriz de ceil(n/32.)ints de 32 bits. Você pode então trabalhar com o array numpy da mesma maneira (bem, semelhante o suficiente) que você usa ints, incluindo usá-los para indexar outro array.

O algoritmo consiste basicamente em calcular, em paralelo, o número de bits definido em cada célula, e eles somam a contagem de bits de cada célula.

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

Embora esteja surpreso que ninguém tenha sugerido que você escrevesse um módulo C.

Leewz
fonte
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
fonte
-2

Acontece que sua representação inicial é uma lista de listas de ints que são 1 ou 0. Basta contá-los nessa representação.


O número de bits em um inteiro é constante em python.

No entanto, se você quiser contar o número de bits definidos, a maneira mais rápida é criar uma lista em conformidade com o seguinte pseudocódigo: [numberofsetbits(n) for n in range(MAXINT)]

Isso fornecerá uma pesquisa de tempo constante depois de gerar a lista. Veja a resposta de @PaoloMoretti para uma boa implementação disso. Claro, você não precisa manter tudo isso na memória - você pode usar algum tipo de armazenamento de valor-chave persistente, ou até mesmo MySql. (Outra opção seria implementar seu próprio armazenamento simples baseado em disco).

Marcin
fonte
@StevenRumbalski Por que isso não ajuda?
Marcin
Quando li sua resposta, ela continha apenas sua primeira frase: "O número de bits em um inteiro é constante em python."
Steven Rumbalski
Já tenho uma tabela de consulta de contagem de bits para todas as contagens que é possível armazenar, mas ter uma grande lista de números e operá-los com um [i] e a [j] torna sua solução inútil, a menos que eu tenha mais de 10 GB de RAM. array para & ^ | para triplos de 10.000 números seria 3 * 10.000 ^ 3 tamanho da tabela de pesquisa. já que não sei do que vou precisar, faz mais sentido contar apenas alguns milhares quando eu precisar deles
zidarsk8
@ zidarsk8 Ou você pode usar algum tipo de banco de dados ou armazenamento persistente de valor-chave.
Marcin,
@ zidarsk8 10 + GB de RAM não é muito grande. Se você deseja realizar cálculos numéricos rápidos, é razoável usar ferro médio-grande.
Marcin,