Подтвердить что ты не робот

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

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

bin(n).count("1")

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

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

Редактировать: 1. это должно быть в Python 2.7 или 2.6

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

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

12448057941136394342297748548545082997815840357634948550739612798732309975923280685245876950055614362283769710705811182976142803324242407017104841062064840113262840137625582646683068904149296501029754654149991842951570880471230098259905004533869130509989042199261339990315125973721454059973605358766253998615919997174542922163484086066438120268185904663422979603026066685824578356173882166747093246377302371176167843247359636030248569148734824287739046916641832890744168385253915508446422276378715722482359321205673933317512861336054835392844676749610712462818600179225635467147870208L
4b9b3361

ОТВЕТЫ

Ответ 1

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

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

С другой стороны, gmpy popcount() занимал около 1/20 времени 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.

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

Ответ 3

Здесь реализована реализация алгоритма подсчета популяции на 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

В соответствии с этим post, это, по-видимому, одна из самых быстрых реализаций Вес Хэмминга (если вы не против использования около 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 - это C-кодированный модуль расширения Python, который обертывает библиотеку GMP.

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

Ответ 5

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

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

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

Ответ 6

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

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

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

setup = """
import numpy as np
#Using Paolo Moretti 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.

Ответ 7

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

Ответ 8

number = 789 number.bit_length()

Ответ 9

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

Ответ 10

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

Число битов в целых числах является константой в python.

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

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