Cara cepat menghitung bit bukan nol dalam bilangan bulat positif

Saya membutuhkan cara cepat untuk menghitung jumlah bit dalam integer dengan python. Solusi saya saat ini adalah

bin(n).count("1")

tetapi saya bertanya-tanya apakah ada cara yang lebih cepat untuk melakukan ini?

PS: (Saya mewakili array biner 2D besar sebagai satu daftar angka dan melakukan operasi bitwise, dan itu membawa waktu turun dari jam ke menit. Dan sekarang saya ingin membuang menit ekstra itu.

Edit: 1. harus di python 2.7 atau 2.6

dan mengoptimalkan angka kecil tidak terlalu menjadi masalah karena itu tidak akan menjadi hambatan yang jelas, tetapi saya memiliki angka dengan 10.000 + bit di beberapa tempat

misalnya ini adalah kasus 2000 bit:

12448057941136394342297748548545082997815840357634948550739612798732309975923280685245876950055614362283769710705811182976142803324242407017104841062064840113262840137625582646683068904149296501029754654149991842951570880471230098259905004533869130509989042199261339990315125973721454059973605358766253998615919997174542922163484086066438120268185904663422979603026066685824578356173882166747093246377302371176167843247359636030248569148734824287739046916641832890744168385253915508446422276378715722482359321205673933317512861336054835392844676749610712462818600179225635467147870208L

Untuk bilangan bulat dengan panjang arbitrer, bin(n).count("1")adalah yang tercepat yang dapat saya temukan di Python murni.

Saya mencoba mengadaptasi solusi Óscar dan Adam untuk memproses integer masing-masing dalam potongan 64-bit dan 32-bit. Keduanya setidaknya sepuluh kali lebih lambat dari bin(n).count("1")(versi 32-bit membutuhkan waktu sekitar setengahnya lagi).

Di sisi lain, gmpy popcount() memakan waktu sekitar 1/20 waktu bin(n).count("1"). Jadi, jika Anda dapat menginstal gmpy, gunakan itu.

Untuk menjawab pertanyaan di komentar, untuk byte saya akan menggunakan tabel pencarian. Anda dapat membuatnya saat runtime:

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

Atau cukup definisikan secara harfiah:

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

Maka itu counts[x]untuk mendapatkan jumlah 1 bit di xmana 0 ≤ x ≤ 255.

Anda dapat mengadaptasi algoritma berikut:

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

Ini berfungsi untuk bilangan positif 64-bit, tetapi mudah diperpanjang dan jumlah operasi bertambah dengan logaritma argumen (yaitu secara linier dengan ukuran bit argumen).

Untuk memahami cara kerjanya, bayangkan Anda membagi seluruh string 64-bit menjadi 64 keranjang 1-bit. Setiap nilai keranjang sama dengan jumlah bit yang disetel dalam keranjang (0 jika tidak ada bit yang disetel dan 1 jika satu bit disetel). Hasil transformasi pertama dalam keadaan analog, tetapi dengan 32 bucket masing-masing sepanjang 2-bit. Hal ini dicapai dengan menggeser bucket secara tepat dan menambahkan nilainya (satu penambahan akan menangani semua bucket karena tidak ada muatan yang dapat terjadi di seluruh bucket - nomor n-bit selalu cukup panjang untuk mengenkode angka n). Transformasi lebih lanjut menghasilkan status dengan jumlah bucket yang semakin berkurang secara eksponensial dengan ukuran yang tumbuh secara eksponensial hingga kami menemukan satu bucket dengan panjang 64-bit. Ini memberikan jumlah bit yang disetel dalam argumen asli.

Berikut implementasi Python dari algoritma penghitungan populasi, seperti yang dijelaskan dalam posting ini :

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

Ini akan berhasil 0 <= i < 0x100000000.

Menurut posting ini , ini tampaknya menjadi salah satu implementasi tercepat dari bobot Hamming (jika Anda tidak keberatan menggunakan memori sekitar 64KB).

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

Pada Python 2.x Anda harus mengganti rangedengan xrange.

Sunting

Jika Anda membutuhkan kinerja yang lebih baik (dan angka Anda adalah bilangan bulat besar), lihat GMPperpustakaan. Ini berisi implementasi perakitan tulisan tangan untuk banyak arsitektur yang berbeda.

gmpy adalah modul ekstensi Python berkode C yang membungkus pustaka GMP.

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

Saya sangat suka metode ini. Sederhana dan cukup cepat tetapi juga tidak terbatas dalam panjang bit karena python memiliki bilangan bulat tak terbatas.

Ini sebenarnya lebih licik daripada yang terlihat, karena menghindari membuang-buang waktu memindai nol. Misalnya, akan memakan waktu yang sama untuk menghitung bit yang ditetapkan dalam 1000000000000000000000010100000001 seperti pada 1111.

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

Anda dapat menggunakan algoritme untuk mendapatkan string biner [1] dari sebuah bilangan bulat tetapi alih-alih menggabungkan string, menghitung jumlah yang:

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

Anda bilang Numpy terlalu lambat. Apakah Anda menggunakannya untuk menyimpan bit individual? Mengapa tidak memperluas gagasan menggunakan int sebagai larik bit tetapi menggunakan Numpy untuk menyimpannya?

Simpan n bit sebagai larik ceil(n/32.)int 32-bit. Anda kemudian dapat bekerja dengan numpy array dengan cara yang sama (baik, cukup mirip) seperti Anda menggunakan int, termasuk menggunakannya untuk mengindeks array lain.

Algoritme ini pada dasarnya untuk menghitung, secara paralel, jumlah bit yang ditetapkan di setiap sel, dan menjumlahkan bitcount setiap sel.

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

Meskipun saya terkejut tidak ada yang menyarankan Anda menulis modul C.

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

Ternyata representasi awal Anda adalah daftar daftar int yang bisa 1 atau 0. Hitung saja dalam representasi itu.

Jumlah bit dalam integer konstan dalam python.

Namun, jika Anda ingin menghitung jumlah set bit, cara tercepat adalah membuat daftar yang sesuai dengan pseudocode berikut: [numberofsetbits(n) for n in range(MAXINT)]

Ini akan memberi Anda pencarian waktu yang konstan setelah Anda membuat daftar. Lihat jawaban @ PaoloMoretti untuk implementasi yang baik dari ini. Tentu saja, Anda tidak harus menyimpan semua ini dalam memori - Anda dapat menggunakan semacam penyimpanan nilai kunci yang persisten, atau bahkan MySql. (Pilihan lain adalah menerapkan penyimpanan berbasis disk sederhana Anda sendiri).