[PYTHON] 양의 정수로 0이 아닌 비트를 빠르게 계산

양의 정수로 0이 아닌 비트를 빠르게 계산

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

bin(n).count("1")

그러나 이것을 수행하는 더 빠른 방법이 있는지 궁금합니다.

추신 : (숫자의 단일 목록으로 큰 2D 바이너리 배열을 표현하고 비트 연산을 수행하고 시간이 몇 분에서 몇 분으로 줄어들어 이제 여분의 분을 없애고 싶습니다.

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

작은 숫자를 최적화하는 것은 그다지 중요하지 않습니다. 왜냐하면 그 것이 명확한 병 목이 아니기 때문이죠.하지만 어떤 곳에서는 10 000 + 비트가있는 숫자가 있습니다.

예를 들어 이것은 2000 비트의 경우입니다.

12448057941136394342297748548545082997815840357634948550739612798732309975923280685245876950055614362283769710705811182976142803324242407017104841062064840113262840137625582646683068904149296501029754654149991842951570880471230098259905004533869130509989042199261339990315125973721454059973605358766253998615919997174542922163484086066438120268185904663422979603026066685824578356173882166747093246377302371176167843247359636030248569148734824287739046916641832890744168385253915508446422276378715722482359321205673933317512861336054835392844676749610712462818600179225635467147870208L

해결법

1. ==============================

   1.임의의 정수의 경우, bin (n) .count ( "1")는 순수 파이썬에서 가장 빠른 정수입니다.

   임의의 정수의 경우, bin (n) .count ( "1")는 순수 파이썬에서 가장 빠른 정수입니다.

   필자는 64 비트 및 32 비트 청크로 정수를 처리하기 위해 Óscar와 Adam의 솔루션을 적용 해 보았습니다. 두 가지 모두 bin (n) .count ( "1")보다 10 배 이상 느립니다 (32 비트 버전은 많은 시간이 소요되었습니다).

   반면에 gmpy popcount ()는 bin (n) .count ( "1") 시간의 약 1/20을 사용했습니다. 그래서 gmpy를 설치할 수 있다면 그것을 사용하십시오.

2. ==============================

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

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

   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). 첫 번째 변환은 비슷한 상태가되지만 각 2 비트 길이의 32 개 버킷이 있습니다. 이는 버킷을 적절하게 이동시키고 값을 더함으로써 달성됩니다 (버킷에 캐리가 발생할 수 없기 때문에 하나의 추가가 모든 버킷을 처리합니다 .- n 비트의 숫자는 항상 숫자 n을 인코딩 할만큼 충분히 길기 때문입니다). 추가 변환은 하나의 64 비트 버킷에 도착할 때까지 기하 급수적으로 증가하는 버킷 수를 기하 급수적으로 감소시키는 상태로 이어진다. 이것은 원래 인수에 설정된 비트 수를 제공합니다.

3. ==============================

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

   다음은이 게시물에서 설명한대로 인구수 계산 알고리즘의 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에서 작동합니다.

4. ==============================

   4.이 게시물에 따르면,이 중 하나가 해밍 무게의 가장 빠른 구현 인 것 같습니다 (약 64KB의 메모리 사용에 신경 쓰지 않는다면).

   이 게시물에 따르면,이 중 하나가 해밍 무게의 가장 빠른 구현 인 것 같습니다 (약 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
   

5. ==============================

   5.너는 낸피가 너무 느리다 고 말했다. 개별 비트를 저장하는 데 사용 했습니까? int를 비트 배열로 사용하는 생각을 확장하지 않고 Numpy를 사용하여 그 배열을 저장하는 것이 어떻습니까?

   너는 낸피가 너무 느리다 고 말했다. 개별 비트를 저장하는 데 사용 했습니까? int를 비트 배열로 사용하는 생각을 확장하지 않고 Numpy를 사용하여 그 배열을 저장하는 것이 어떻습니까?

   n 비트를 ceil (n / 32.) 32 비트 int 배열로 저장하십시오. 그런 다음 numpy 배열을 사용하여 정수를 사용하여 다른 배열을 색인화하는 방법을 포함하여 int와 같은 방식으로 작업 할 수 있습니다.

   이 알고리즘은 기본적으로 각 셀에 설정된 비트 수를 병렬로 계산하며, 각 셀의 비트 수를 합산합니다.

   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
   

   놀랍지 만 아무도 C 모듈을 쓸 것을 제안하지 않았습니다.

6. ==============================

   6.이 알고리즘을 사용하여 정수의 2 진 문자열 [1]을 얻을 수 있지만 문자열을 연결하는 대신 1의 수를 계산합니다.

   이 알고리즘을 사용하여 정수의 2 진 문자열 [1]을 얻을 수 있지만 문자열을 연결하는 대신 1의 수를 계산합니다.

   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

7. ==============================

   7.시작 표현은 1 또는 0 인 int 목록의 목록입니다. 간단히 그 표현으로 계산하십시오.

   시작 표현은 1 또는 0 인 int 목록의 목록입니다. 간단히 그 표현으로 계산하십시오.

   정수의 비트 수는 파이썬에서 일정합니다.

   그러나 설정 비트 수를 계산하려는 경우 가장 빠른 방법은 다음 의사 코드를 준수하는 목록을 만드는 것입니다. [numberofsetbits (n) for n range (MAXINT)]

   이렇게하면 목록을 생성 한 후 일정 시간 조회가 제공됩니다. 이것의 좋은 구현에 대한 @ PaoloMoretti의 답변을 참조하십시오. 물론이 모든 것을 메모리에 보관할 필요는 없습니다. 영구적 인 키 - 값 저장소 또는 MySql을 사용할 수 있습니다. (또 다른 옵션은 자신 만의 간단한 디스크 기반 스토리지를 구현하는 것입니다.)

from https://stackoverflow.com/questions/9829578/fast-way-of-counting-non-zero-bits-in-positive-integer by cc-by-sa and MIT license