Быстрый способ подсчета ненулевых битов в натуральном числе - PullRequest
Новая
       18

Быстрый способ подсчета ненулевых битов в натуральном числе

97 голосов
/ 22 марта 2012

Мне нужен быстрый способ подсчитать количество бит в целом числе в Python. Мои текущие решения 

bin(n).count("1")

но мне интересно, есть ли более быстрый способ сделать это?

PS: (Я представляю большой двумерный двоичный массив в виде единого списка чисел и выполняю побитовые операции, и это сокращает время с часов до минут. Теперь я хотел бы избавиться от этих лишних минут.

Edit: 1. должно быть в python 2.7 или 2.6

и оптимизация для небольших чисел не имеет большого значения, так как это не будет четкой горловиной, но у меня есть числа с 10 000 + битами в некоторых местах

например, это 2000-битный регистр: 

12448057941136394342297748548545082997815840357634948550739612798732309975923280685245876950055614362283769710705811182976142803324242407017104841062064840113262840137625582646683068904149296501029754654149991842951570880471230098259905004533869130509989042199261339990315125973721454059973605358766253998615919997174542922163484086066438120268185904663422979603026066685824578356173882166747093246377302371176167843247359636030248569148734824287739046916641832890744168385253915508446422276378715722482359321205673933317512861336054835392844676749610712462818600179225635467147870208L

Ответы [ 9 ]

105 голосов
/ 23 марта 2012

Для целых чисел произвольной длины bin(n).count("1") - самое быстрое, что я мог найти в чистом Python.

Я попытался адаптировать решения Оскара и Адама для обработки целых чисел в 64-битных и 32-битных блоках соответственно,Оба были как минимум в десять раз медленнее, чем bin(n).count("1") (32-битная версия заняла примерно вдвое больше времени).

С другой стороны, gmpy popcount() заняло около 120 числа 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')

Тогда counts[x], чтобы получить число 1 бит в x, где 0 ≤x ≤ 255.

22 голосов
/ 23 марта 2012

Вы можете адаптировать следующий алгоритм: 

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, если установлен один бит).Первое преобразование приводит к аналогичному состоянию, но с 32 сегментами каждый 2-битный.Это достигается путем соответствующего смещения сегментов и добавления их значений (одно добавление заботится обо всех сегментах, поскольку перенос не может происходить через сегменты - n-битное число всегда достаточно длинное, чтобы кодировать число n).Дальнейшие преобразования приводят к состояниям с экспоненциально уменьшающимся количеством сегментов экспоненциально растущего размера, пока мы не достигнем одного 64-битного сегмента.Это дает количество битов, установленных в исходном аргументе.

13 голосов
/ 23 марта 2012

Вот реализация Python алгоритма подсчета населения, как описано в этом post : 

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.

8 голосов
/ 23 марта 2012

Согласно этому сообщению , это, кажется, одна из самых быстрых реализаций веса Хэмминга (если вы не возражаете против использования около 64 КБ памяти). 

#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 - это модуль расширения Python на C-коде, заключающий в себе библиотеку GMP. 

>>> import gmpy
>>> gmpy.popcount(2**1024-1)
1024
2 голосов
/ 25 апреля 2019

Мне очень нравится этот метод. Это просто и довольно быстро, но также не ограничено в битовой длине, так как python имеет бесконечные целые числа.

На самом деле это более хитро, чем кажется, потому что он не тратит время на сканирование нулей. Например, для подсчета установленных бит в 1000000000000000000000010100000001 потребуется столько же времени, сколько в 1111. 

def get_bit_count(value):
   n = 0
   while value:
      n += 1
      value &= value-1
   return n
2 голосов
/ 03 мая 2014

Вы сказали, что Numpy был слишком медленным.Вы использовали его для хранения отдельных битов?Почему бы не расширить идею использования ints в качестве битовых массивов, а использовать Numpy для их хранения?

Хранить n битов в виде массива ceil(n/32.) 32-битных int.Затем вы можете работать с массивом NumPy таким же (достаточно похожим) способом, как вы используете целые, включая их использование для индексации другого массива.

Алгоритм в основном для параллельного вычисления количества установленных битов.в каждой ячейке, и они суммируют количество бит каждой ячейки. 

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.

1 голос
/ 31 августа 2017

Вы можете использовать алгоритм, чтобы получить двоичную строку [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

0 голосов
/ 15 июня 2019 
#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)
0 голосов
/ 23 марта 2012

Оказывается, ваше начальное представление - это список списков целых чисел, которые равны либо 1, либо 0. Просто посчитайте их в этом представлении..

Однако, если вы хотите посчитать количество установленных бит, самый быстрый способ - создать список, соответствующий следующему псевдокоду: [numberofsetbits(n) for n in range(MAXINT)]

Это обеспечит вам постоянное времяпоиск после того, как вы сгенерировали список.Посмотрите ответ @ PaoloMoretti для хорошей реализации этого.Конечно, вам не нужно хранить все это в памяти - вы можете использовать какое-то постоянное хранилище значений ключей или даже MySql.(Другой вариант - реализовать собственное простое дисковое хранилище).

...