양의 정수에서 0이 아닌 비트를 계산하는 빠른 방법

양의 정수에서 0이 아닌 비트를 계산하는 빠른 방법

---

파이썬에서 정수의 비트 수를 계산하는 빠른 방법이 필요합니다. 내 현재 솔루션은

bin(n).count("1")

하지만 더 빠른 방법이 있는지 궁금합니다.

추신 : (나는 큰 2D 이진 배열을 단일 숫자 목록으로 나타내고 비트 연산을 수행하고 있으며, 그로 인해 시간이 몇 시간에서 몇 분으로 단축됩니다. 이제 그 여분의 분을 없애고 싶습니다.

편집 : 1. 파이썬 2.7 또는 2.6에 있어야합니다.

그리고 작은 숫자에 대한 최적화는 명확한 병목 현상이 아니기 때문에 그다지 중요하지 않지만 일부 장소에는 10,000 + 비트의 숫자가 있습니다.

예를 들어 이것은 2000 비트 케이스입니다.

12448057941136394342297748548545082997815840357634948550739612798732309975923280685245876950055614362283769710705811182976142803324242407017104841062064840113262840137625582646683068904149296501029754654149991842951570880471230098259905004533869130509989042199261339990315125973721454059973605358766253998615919997174542922163484086066438120268185904663422979603026066685824578356173882166747093246377302371176167843247359636030248569148734824287739046916641832890744168385253915508446422276378715722482359321205673933317512861336054835392844676749610712462818600179225635467147870208L

---

임의 길이 정수의 경우 bin(n).count("1")순수한 Python에서 찾을 수있는 가장 빠른 것입니다.

저는 Óscar와 Adam의 솔루션을 적용하여 정수를 각각 64 비트와 32 비트 청크로 처리했습니다. 둘 다 적어도 10 배 더 느 렸습니다 bin(n).count("1")(32 비트 버전은 시간이 절반 정도 걸렸습니다).

반면에 gmpy popcount() 는 bin(n).count("1"). 따라서 gmpy를 설치할 수 있다면 그것을 사용하십시오.

주석의 질문에 답하기 위해 바이트에 대해 조회 테이블을 사용합니다. 런타임에 생성 할 수 있습니다.

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

또는 문자 그대로 정의하십시오.

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

그런 다음 0 ≤ x ≤ 255 counts[x]인 1 비트 수를 가져옵니다 x.

---

다음 알고리즘을 적용 할 수 있습니다.

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

이는 64 비트 양수에 대해 작동하지만 쉽게 확장 할 수 있으며 인수의 로그에 따라 연산 수가 증가합니다 (즉, 인수의 비트 크기에 따라 선형 적으로).

이것이 어떻게 작동하는지 이해하기 위해 전체 64 비트 문자열을 64 개의 1 비트 버킷으로 나눈다 고 상상해보십시오. 각 버킷의 값은 버킷에 설정된 비트 수와 같습니다 (비트가 설정되지 않은 경우 0, 1 비트가 설정된 경우 1). 첫 번째 변환은 유사한 상태가되지만 각 2 비트 길이의 버킷이 32 개 있습니다. 이는 버킷을 적절하게 이동하고 값을 추가하여 수행됩니다 (버킷간에 캐리가 발생하지 않으므로 한 번만 추가하면 모든 버킷이 처리됩니다. n 비트 숫자는 항상 숫자 n을 인코딩하기에 충분합니다). 추가 변환은 하나의 64 비트 길이 버킷에 도달 할 때까지 기하 급수적으로 증가하는 크기의 버킷 수를 기하 급수적으로 감소시키는 상태로 이어집니다. 이것은 원래 인수에 설정된 비트 수를 제공합니다.

---

다음은이 게시물 에서 설명한대로 인구 수 알고리즘의 Python 구현입니다 .

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

에서 작동합니다 0 <= i < 0x100000000.

---

이 게시물 에 따르면 이것은 Hamming 가중치를 가장 빠르게 구현 한 것 같습니다 (약 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])

Python 2.x range에서는 xrange.

편집하다

더 나은 성능이 필요하고 숫자가 큰 정수인 경우 GMP라이브러리를 살펴보십시오 . 여기에는 다양한 아키텍처에 대한 손으로 작성한 어셈블리 구현이 포함되어 있습니다.

gmpy GMP 라이브러리를 래핑하는 C 코딩 된 Python 확장 모듈입니다.

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

---

이 방법이 정말 마음에 듭니다. 간단하고 매우 빠르지 만 파이썬에는 무한한 정수가 있기 때문에 비트 길이가 제한되지 않습니다.

It's actually more cunning than it looks, because it avoids wasting time scanning the zeros. For example it will take the same time to count the set bits in 1000000000000000000000010100000001 as in 1111.

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

---

You said Numpy was too slow. Were you using it to store individual bits? Why not extend the idea of using ints as bit arrays but use Numpy to store those?

Store n bits as an array of ceil(n/32.) 32-bit ints. You can then work with the numpy array the same (well, similar enough) way you use ints, including using them to index another array.

The algorithm is basically to compute, in parallel, the number of bits set in each cell, and them sum up the bitcount of each 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

Though I'm surprised no one suggested you write a C module.

---

You can use the algorithm to get the binary string [1] of an integer but instead of concatenating the string, counting the number of ones:

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

---

It turns out your starting representation is a list of lists of ints which are either 1 or 0. Simply count them in that representation.

---

The number of bits in an integer is constant in python.

However, if you want to count the number of set bits, the fastest way is to create a list conforming to the following pseudocode: [numberofsetbits(n) for n in range(MAXINT)]

This will provide you a constant time lookup after you have generated the list. See @PaoloMoretti's answer for a good implementation of this. Of course, you don't have to keep this all in memory - you could use some sort of persistent key-value store, or even MySql. (Another option would be to implement your own simple disk-based storage).

참고URL : https://stackoverflow.com/questions/9829578/fast-way-of-counting-non-zero-bits-in-positive-integer