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

117

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

bin(n).count("1")

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

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

Изменить: 1. он должен быть в Python 2.7 или 2.6

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

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

12448057941136394342297748548545082997815840357634948550739612798732309975923280685245876950055614362283769710705811182976142803324242407017104841062064840113262840137625582646683068904149296501029754654149991842951570880471230098259905004533869130509989042199261339990315125973721454059973605358766253998615919997174542922163484086066438120268185904663422979603026066685824578356173882166747093246377302371176167843247359636030248569148734824287739046916641832890744168385253915508446422276378715722482359321205673933317512861336054835392844676749610712462818600179225635467147870208L
zidarsk8
источник
Связанный: stackoverflow.com/questions/407587/…
Душан
1
Какое представление вы используете, если ваши «целые числа» длиннее стандартного питона int? Разве у этого нет собственного метода расчета этого?
Marcin
1
возможное дублирование битов Count целого числа в Python
endolith
3
Чтобы отличить вопрос от вопроса в stackoverflow.com/a/2654211/1959808 (если предполагается, что он будет другим - по крайней мере, так выглядит), пожалуйста, подумайте о перефразировании заголовка на «... подсчет количества не- нулевые биты ... »или подобное. В противном случае int.bit_lengthдолжен быть ответ, а не тот, который принят ниже.
Иоаннис Филиппидис

Ответы:

121

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

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

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

Kindall
источник
7
+1! Обратное утверждение неверно, однако следует указать: bin(n).count("0")неточно из-за префикса «0b». bin(n)[2:].count('0')Должен быть для тех, кто считает непослушных ....
волк
11
Однако вы не можете подсчитать нулевые биты, не зная, сколько байтов вы заполняете, что проблематично для длинного целого числа Python, потому что это может быть что угодно.
kindall
2
Хотя это быстрые варианты для одиночных целых чисел, обратите внимание, что алгоритмы, представленные в других ответах, потенциально могут быть векторизованы, что намного быстрее, если они работают со многими элементами большого numpyмассива.
gerrit
Для массивов numpy я бы посмотрел примерно так: gist.github.com/aldro61/f604a3fa79b3dec5436a
kindall
1
Я использовал bin(n).count("1"). Однако это превосходит только 60% представления Python. @ leetcode
northtree
30

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

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-битного сегмента. Это дает количество битов, установленных в исходном аргументе.

Адам Зальцман
источник
Я серьезно понятия не имею, как это будет работать с 10 000-битными числами, но решение мне нравится. Можете ли вы дать мне подсказку, если и как я могу применить это к большим числам?
zidarsk8
Я не видел, сколько битов вы здесь имеете. Думали ли вы о написании кода обработки данных на языке низкого уровня, таком как C? Возможно, как расширение вашего кода на Python? Вы, безусловно, можете улучшить производительность, используя большие массивы в C по сравнению с большими числами в python. Тем не менее, вы можете переписать CountBits()для обработки 10-битных чисел, добавив всего 8 строк кода. Но он станет громоздким из-за огромных констант.
Адам Зальцман,
2
Вы можете написать код для генерации последовательности констант и настроить цикл для обработки.
Карл Кнехтель,
Этот ответ имеет большое преимущество в том, что его можно векторизовать для случаев, связанных с большими numpyмассивами.
gerrit
17

Вот реализация 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.

Оскар Лопес
источник
Это умно. Полностью уместно смотреть на это вместо того, чтобы стрелять в ответ от бедра!
MrGomez
1
Вы это тестировали? На моей машине, использующей python 2.7, я обнаружил, что это на самом деле немного медленнее, чем bin(n).count("1").
Дэвид Уэлдон
@DavidWeldon Нет, не мог, не могли бы вы опубликовать свои тесты?
Оскар Лопес,
%timeit numberOfSetBits(23544235423): 1000000 loops, best of 3: 818 ns per loop; %timeit bitCountStr(23544235423): 1000000 loops, best of 3: 577 ns per loop.
gerrit
7
Однако numberOfSetBitsобрабатывает мой 864 × 64 numpy.ndarrayза 841 мкс. С bitCountStrя должен явно зацикливаться, и это занимает 40,7 мс, или почти в 50 раз больше.
gerrit
8

Согласно этому сообщению , это одна из самых быстрых реализаций веса Хэмминга (если вы не против использования около 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
Паоло Моретти
источник
Я отредактировал свой вопрос, чтобы пояснить, что мне нужно это для больших чисел (10k бит и более). оптимизация чего-либо для 32-битных целых чисел, вероятно, не будет иметь большого значения, поскольку количество отсчетов должно быть очень большим, и в этом случае это приведет к медленному времени выполнения.
zidarsk8
Но GMP предназначен именно для очень больших чисел, в том числе для чисел, не превышающих указанных вами.
Джеймс Янгман
1
Использование памяти будет лучше, если вы используете array.arrayfor POPCOUNT_TABLE16, поскольку тогда он будет храниться как массив целых чисел, а не как список intобъектов Python с динамическим размером .
gsnedders
6

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

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

def get_bit_count(value):
   n = 0
   while value:
      n += 1
      value &= value-1
   return n
Robotbugs
источник
выглядит отлично, но подходит только для очень "разреженных" целых чисел. в среднем это довольно медленно. Тем не менее, в некоторых случаях это выглядит действительно полезным.
zidarsk8
Я не совсем понимаю, что вы имеете в виду под «в среднем довольно медленно». Довольно медленно по сравнению с чем? Вы имеете в виду медленный по сравнению с другим кодом Python, который вы не цитируете? Это в два раза быстрее, чем побитовый подсчет среднего числа. Фактически, на моем MacBook он насчитывает 12,6 миллиона бит в секунду, что намного быстрее, чем я могу их считать. Если у вас есть другой общий алгоритм Python, который работает для любой длины целого числа и быстрее этого, я бы хотел услышать об этом.
Robotbugs
1
Я согласен с тем, что на самом деле это медленнее, чем ответ Мануэля выше.
Robotbugs
В среднем довольно медленно означает, что подсчет бит для 10000 чисел с 10000 цифрами занимает 0,15 с, bin(n).count("1")но для вашей функции потребовалось 3,8 с. Если бы в числах было установлено очень мало битов, он работал бы быстро, но если вы возьмете любое случайное число, в среднем вышеуказанная функция будет работать на порядки медленнее.
zidarsk8
Хорошо, я приму это. Думаю, я просто был придурком, потому что ты немного неточный, но ты совершенно прав. Я просто не тестировал метод с использованием метода Мануэля выше до своего комментария. Это выглядит очень неуклюже, но на самом деле очень быстро. Сейчас я использую такую ​​версию, но с 16 значениями в словаре, и это даже намного быстрее, чем та, которую он процитировал. Но для записи я использовал свой в приложении только с несколькими битами, которые были установлены в 1. Но для полностью случайных битов да, это будет примерно 50:50 с небольшой дисперсией, уменьшающейся с длиной.
Robotbugs
3

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

Manuel
источник
Это работает быстро. Ошибка, по крайней мере, на p3, [1:] должно быть [2:], потому что oct () возвращает '0o' перед строкой. Код работает намного быстрее, если вы используете hex () вместо oct () и делаете словарь из 16
статей
2

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

Храните n битов как массив ceil(n/32.)32-битных целых чисел. Затем вы можете работать с массивом 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.

leewz
источник
0
#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)
Правин Нарала
источник
-2

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


Количество бит в целом числе в Python постоянно.

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

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

Marcin
источник
@StevenRumbalski Как это бесполезно?
Marcin
Когда я прочитал ваш ответ, он содержал только ваше первое предложение: «Число битов в целом числе в Python постоянно».
Стивен Румбальский,
У меня уже есть таблица поиска для всех подсчетов, которые можно сохранить, но наличие большого списка чисел и работа с ними с помощью a [i] и a [j] делает ваше решение бесполезным, если у меня нет 10+ ГБ оперативной памяти. массив для & ^ | для троек из 10000 номеров будет размер таблицы поиска 3 * 10000 ^ 3. так как я не знаю, что мне понадобится, имеет смысл просто сосчитать несколько тысяч, когда они мне понадобятся
zidarsk8
@ zidarsk8 Или вы можете использовать какую-то базу данных или постоянное хранилище значений ключей.
Marcin
@ zidarsk8 10+ ГБ оперативной памяти шокирует не много. Если вы хотите выполнить быстрые численные вычисления, вполне разумно использовать железо среднего и большого размера.
Marcin