Битовое программирование на Python

Question

Я пытаюсь написать программу для решения проблемы ACM, и она должна быть очень быстрой. Математически быстрый подход к проблеме состоит в использовании побитовых вычислений. Тем не менее, я использую Python и у меня возникают проблемы при выполнении этих вычислений на уровне битов. Проблемы:

1. Подсчет количества 1 и 0 в бите. Например, как мы вычисляем, что двоичная цифра 100010 имеет два 1 и 4 0. Единственный подход, который я могу себе представить, - это преобразовать его в строку и сосчитать их. Но это преобразование сводит на нет всю скорость, полученную при работе на битовом уровне.
2. Как представить строковый ввод, описывающий двоичную цифру, такую ​​как "100101", как фактическую двоичную цифру в Python? В настоящее время у меня есть функция, которая преобразует бит в целое число, и я выполняю побитовые операции над целыми числами.
3. Есть ли немного тип данных? То есть я могу получить ввод как бит, а не как строку или целое число?

Я действительно думал написать класс, такой как bitSet, в C++, но у меня есть ощущение, что это будет не очень быстро. PS двоичные цифры, с которыми я работаю, могут достигать 1000 бит, и мне, возможно, придется работать с 1000 такими двоичными цифрами, поэтому эффективность является обязательной.

Answer 1

Вот хорошо известный алгоритм подсчета однобитных данных:

def bitCount(x):
    count = 0
    while x != 0:
       count += 1
       x &= (x-1)
    return count

Дело в том, что x-1 имеет то же двоичное представление, что и x, за исключением того, что младший младший бит сбрасывается в 0, а все завершающие 0 устанавливаются в единицу. Итак, настройка x = x & (x-1) просто очищает младший значащий бит.