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

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

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

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

return c

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

Answer 2

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

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

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

В любом случае: если вы действительно спрашивали о вычислительной сложности, что, в частности, означает анализ больших чисел, это ваш ответ. : -)

Answer 3

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

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

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

Answer 4

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

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

Answer 5

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

Answer 6

Здесь:

def 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), так как она запускает количество раз, сколько единиц существует в двоичном файле.

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