Как я могу проверить вес Хэмминга без преобразования в двоичный формат?

Question

Как я могу получить количество «1» в двоичном представлении числа без фактического преобразования и подсчета?

например

  def number_of_ones(n):
      # do something
      # I want to MAKE this FASTER (computationally less complex).
      c = 0
      while n:
        c += n%2
        n /= 2
      return c


>>> number_of_ones(5)
    2
>>> number_of_ones(4)
    1

Answer 1

IMO, хорошим подходом было бы использовать справочную таблицу - создать словарь, который преобразует байты в число единиц (вы можете использовать опубликованный вами код для его создания, его нужно будет запустить только один раз), а затем использовать что-нибудь так:

def number_of_ones(n):
    sum = 0
    while n != 0:
        sum += lookup_table[n & 0xff]
        n >>= 8
    return sum

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

Answer 2

Я не программист на Python, но, надеюсь, вам этого будет достаточно.

c = 0
while n:
    c += 1
    n &= n - 1

return c

Хотя это немного неясно, его основным преимуществом является скорость и простота.Цикл while повторяется только один раз для каждого бита, установленного в 1 в n.

Answer 3

Вы не можете сделать это вычислительно менее сложным.Это будет O(n) количество битов или, как показал ответ с трюком &, O(n) количество битов, установленных в 1;но если все числа, которые вы используете, не являются особым случаем, последние в среднем должны быть равны n/2, поэтому оба числа O(n) одинаковы.

И трюк со справочной таблицей, конечно, на самом деле никак не влияет на сложность вычислений;это просто оплата времени пространством, но без изменения базовой экономики, которая заключается в том, что вы должны один раз проверить каждый бит. как-то и нет никакого способа обойти это.Логически невозможно ответить на вопрос о битах числа, не проверив каждый из них.

Теперь, я полагаю, я немного неряшлив, поскольку многие из этих примеров на самом деле имеют размер O(n^2), поскольку в Python вам нужно проверять все число сразу, поэтому с длинным целым числом Python, скажем, 100 байтов , операция + или & или / будет просматривать каждый байт хотя бы один раз, и это будет происходить снова и снова, пока число не уменьшится до нуля (в схемах, описанных выше), так что это, опять же, действительно O( n^2) операций.Я не уверен, что Python позволит здесь найти истинное решение O(n).

В любом случае:если бы ты действительно спрашивал о вычислительный сложность, которая, в частности, означает анализ «большого О», вот ваш ответ.:-)

Answer 4

Если вы хотите сделать это в одной строке, вы можете использовать:

sum( [x&(1<<i)>0 for i in range(32)] )

Answer 5

Если вас действительно беспокоит скорость, напишите ее на C (см. этот вопрос как это сделать) и взаимодействовать с реализацией C, используя что-то вроде cтипы.

Answer 6

Здесь:

защита bitCount(int_no):

c = 0
while(int_no):
    int_no &= (int_no - 1)
    c += 1
return c

Возможно, это старый и эффективный способ сделать это...изначально реализован на C (имя у Algo я не помню).У меня это работает нормально, надеюсь, что так же будет и у любого другого человека

Answer 7

p= лямбда n:n и 1+p(n&(n-1))

При этом используется короткое замыкание и рекурсия: когда n больше 0, происходит переключение на вычисление 1+p(n&(n-1)), где вызывается p(n&(n-1)) и так далее, когда n равно 0. он возвращает 0.Сложность равна O(n), поскольку она выполняется во столько раз, сколько единиц существует в двоичном формате.

Пример:р(9)=1+р(8)=1+1+р(0)=1+1+0=2