Szybki sposób liczenia niezerowych bitów w dodatniej liczbie całkowitej

Możesz dostosować następujący algorytm:

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

Działa to dla 64-bitowych liczb dodatnich, ale jest łatwo rozszerzalne, a liczba operacji rośnie wraz z logarytmem argumentu (tzn. liniowo z rozmiarem bitów argumentu).

Aby zrozumieć, jak to działa wyobraź sobie, że dzielisz cały 64-bitowy ciąg na 64 1-bitowe wiadra. Wartość każdego zasobnika jest równa liczbie bitów ustawionych w zasobniku (0, jeśli nie są ustawione żadne bity i 1, jeśli jest ustawiony jeden bit). Na pierwsza transformacja powoduje analogiczny stan, ale z 32 wiadrami każda o długości 2-bitowej. Osiąga się to poprzez odpowiednie przesunięcie łyżek i dodanie ich wartości(jeden dodatek zajmuje się wszystkimi łyżkami, ponieważ nie może wystąpić przenoszenie przez łyżki - numer N-bitowy jest zawsze wystarczająco długi, aby zakodować numer n). Dalsze przekształcenia prowadzą do stanów z wykładniczo malejącą liczbą łyżek o wykładniczo rosnącym rozmiarze, aż do uzyskania jednego 64-bitowego długiego wiadra. Daje to liczbę bitów ustawione w oryginalnym argumencie.

Oto implementacja Pythona algorytmu liczenia populacji, jak wyjaśniono w tym poście :

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

Będzie działać dla 0 <= i < 0x100000000.

Zgodnie z tym postem , wydaje się to być jedną z najszybszych implementacji wagi Hamminga (jeśli nie masz nic przeciwko użyciu około 64KB PAMIĘCI).

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

W Pythonie 2.X należy zastąpić range przez xrange.

Edit

Jeśli potrzebujesz lepszej wydajności (a twoje liczby są dużymi liczbami całkowitymi) , spójrz na GMP biblioteka. Zawiera ręcznie pisane implementacje assembly dla wielu różnych architektur.

gmpy na Kodowany w języku C moduł rozszerzenia Pythona, który owija bibliotekę GMP.

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

Bardzo podoba mi się ta metoda. Jego proste i dość szybkie, ale także nie ograniczone w długości bitów, ponieważ python ma nieskończone liczby całkowite.

def get_bit_count(value):
   n = 0
   while value:
      n += 1
      value &= value-1
   return n

Możesz użyć algorytmu, aby uzyskać ciąg binarny[1] liczby całkowitej, ale zamiast łączyć łańcuch, licząc liczbę jedynek:

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

Python 3.10 wprowadza int.bit_count():

>>> n = 19
>>> bin(n)
'0b10011'
>>> n.bit_count()
3
>>> (-n).bit_count()
3

Jest to funkcjonalnie równoważne bin(n).count("1"), ale powinno być~6 razy szybsze . Zobacz też Issue29882 .

Mówiłeś, że Numpy jest zbyt wolny. Używałeś go do przechowywania pojedynczych kawałków? Dlaczego nie rozszerzyć idei używania ints jako tablic bitowych, ale użyć Numpy do ich przechowywania?

Przechowuje n bitów jako tablicę ceil(n/32.) 32-bitowych ints. Następnie możesz pracować z tablicą numpy w ten sam (no cóż, wystarczająco podobny) sposób, w jaki używasz ints, włączając w to użycie ich do indeksowania innej tablicy.

Algorytm polega zasadniczo na obliczeniu, równolegle, liczby bitów ustawionych w każdej komórce i zsumowaniu ich liczby bitów cell.

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

Możliwe jest połączenie tabeli wyszukiwania z int.to_bytes (tylko Python 3):

popcount8bit = bytes([popcount(x) for x in range(1<<8)])  # use any method to initialize this lookup table
popcount = lambda x: sum(map(popcount8bit.__getitem__,
                             x.to_bytes((x.bit_length()+7)//8, "little")))

To rozwiązanie jest niestety o około 20% wolniejsze niż bin(x).count('1') w Pythonie 3, ale dwa razy szybsze na PyPy3.

Jest to skrypt benchmarkowy, porównuje kilka różnych rozwiązań przedstawionych tutaj, dla różnej liczby bitów:

from __future__ import print_function  #for Python 2

import sys
from timeit import timeit
import random

def popcount(x): return bin(x).count("1")

version3=sys.version.startswith("3")

for numBit in (2, 4, 8, 16, 31, 32, 63, 64, 1000, 10000):
    maximum=int((1<<numBit)-1)  #int cast just in case it overflows to long in Python 2

    functions=[
            (popcount, "bin count"),
            (lambda x: "{:b}".format(x).count("1"), "format string count"),
            ]

    try:
        import gmpy
        functions.append((gmpy.popcount, "gmpy"))
    except ImportError:
        pass

    if sys.version.startswith("3"):
        exec('''functions.append((lambda x: f"{x:b}".count("1"), "f-string count"))''')

    if numBit<=16:
        table1=[popcount(x) for x in range(maximum+1)]
        functions.append((lambda x: table1[x], "lookup list"))
        functions.append((table1.__getitem__, "lookup list without lambda"))

        table2="".join(map(chr, table1))
        functions.append((lambda x: ord(table2[x]), "lookup str"))

        if version3:
            table3=bytes(table1)
            functions.append((lambda x: table3[x], "lookup bytes"))

            if numBit==8:
                functions.append((
                        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'
                        .__getitem__, "lookup bytes hard coded 8 bit"))
                table_hardcoded=(
                        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')
                functions.append((
                        table_hardcoded.__getitem__, "lookup bytes hard coded 8 bit local variable"))
            functions.append((table3.__getitem__, "lookup bytes without lambda"))

    if version3:
        popcount8bit=bytes([popcount(x) for x in range(1<<8)]) #bytes because benchmark says that it's fastest
        functions.append((
            lambda x: sum(popcount8bit[x] for x in x.to_bytes((x.bit_length()+7)//8, "big")),
            "to_bytes"
            ))
        functions.append((
            lambda x: sum(map(popcount8bit.__getitem__, x.to_bytes((x.bit_length()+7)//8, "big"))),
            "to_bytes without list comprehension"
            ))
        functions.append((
            lambda x: sum(map(popcount8bit.__getitem__, x.to_bytes((x.bit_length()+7)//8, "little"))),
            "to_bytes little endian, without list comprehension"
            ))

    #for x in (2, 4, 8, 16, 32, 64):
    #   table1=[popcount(x) for x in range(1<<8)]


    print("====== numBit=", numBit)
    data=[]
    numRepeat=10**7//(numBit+100)
    for popcountFunction, description in functions:
        random.seed(10) #make randint returns the same value
        data.append((
            timeit(lambda: popcountFunction(random.randint(0, maximum)), number=numRepeat),
            description
            ))

    time1, name1=data[0]
    assert name1=="bin count"
    data.sort()
    maxLength=0
    for time, description in data:
        maxLength=max(maxLength, len(description))
    for time, description in data:
        print("{:{}} -> {:2f} = {} * {:2f}".format(description, maxLength+2, time, name1, time/time1))

Działa zarówno z Pythonem 2, jak i 3; jednak jeśli rozwiązanie jest niedostępne dla Pythona 2, nie jest mierzone.

Niektóre rozwiązania nie są wymienione proszę.

Wynik:

• Python 2: "Lista odnośników bez lambda" jest najszybsza (25% szybsza niż "bin count", 6% szybsza niż "lookup list" (z lambda)) dla
• Python 3: mniej więcej ten sam wynik.
  • " Lookup bytes without lambda " jest porównywalne (+/-2% w porównaniu do "lookup list without lambda").
  • gmpy jest szybszy niż "bin count" we wszystkich przypadkach, ale wolniejszy niż "lookup list bez lambda" dla około 5% z numBit
  • " to_bytes " jest porównywalne.
  • używanie f-string jest o 10% wolniejsze niż"bin count".
• PyPy3: lambda nie ponosi już dużych kosztów, a wersja to_bytes staje się znacznie szybsza (dwa razy szybciej niż "bin count"); jednak nie mogłem zmusić gmpy do instalacji.

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

Okazuje się, że Twoja reprezentacja startowa jest listą list ints, które są albo 1, albo 0. Po prostu policz je w tej reprezentacji.

Liczba bitów w liczbie całkowitej jest stała w Pythonie.

Jeśli jednak chcesz policzyć liczbę bitów zestawu, najszybszym sposobem jest utworzenie listy zgodnej z następującym pseudokodem: [numberofsetbits(n) for n in range(MAXINT)]

To zapewni Ci stały czas wyszukiwania po wygenerowaniu listy. Zobacz odpowiedź @ PaoloMoretti na dobre realizacja tego. Oczywiście nie musisz trzymać tego wszystkiego w pamięci - możesz użyć pewnego rodzaju trwałego magazynu wartości kluczy, a nawet MySql. (Inną opcją byłoby zaimplementowanie własnej prostej pamięci dyskowej).