анализируя этот алгоритм (большой-O)

Question

Проблема

Что этот алгоритм делает? Что представляет собой 0x01? Что это означает, что m = m >> 1 во внутреннем цикле while? Что это за алгоритм big-O?

while(n>0) 
{ 
    m = n; 
    while(m) 
    { 
      if(m & 0x01) 
      { 
       c++; 
      } 
      m = m >> 1; 
    } 
} 

Покушение

1. Глядя @ алгоритм, я понимаю, что т правильно сдвинутых одно место.
   (Например, если т = 1010, т >> 1 = 0101. Это правильно?)

2. Потому что вложенная в то время как цикл, и потому, что каждый в то время как итерация п раз, я думаю, что этот алгоритм O (N^2). Это верно?

Answer 1

What is this algorithm doing? Для значения n количество бит, находящихся в n, добавляется к c.

0x01 представляет значение 1. Он используется в качестве битовой маски, чтобы проверить, включен ли младший бит m. Если это так, то он увеличивает c. Это часть подсчета бит. Затем m сдвигается вправо один раз, чтобы переместить следующий бит вниз в позицию LSB (младший бит). while(m) остановится один раз m равен 0; то есть, когда m не имеет больше бит.

И алгоритмическая сложность зависит от того, что вы делаете с n. Если вы уменьшаете его, то ваш алгоритм равен O(n), так как внутренний раздел (while(m)) является постоянным (так как максимальное число бит в целых числах, а это, вероятно, 32).

Сложность, вероятно, O(n * 32), но поскольку константы выведены из обозначения Big-Oh, вы получаете O(n).

Answer 2

Внутренний цикл подсчитывает количество бит «1» в м. Его стоимость равна O (log m), так как каждая итерация уменьшает значение m до достижения 0.

(Если вы считаете, что m является целым числом фиксированного размера, скажем, 32 бита, то вы можете сказать внутренний контур равен O (1), поскольку он всегда составляет не более 32 операций, что является постоянным числом)

Внешний контур, как указывали некоторые, никогда не заканчивается, потому что n никогда не изменяется. (если n равно 0).

Так что в целом этот код O (бесконечность), он никогда не заканчивается.

Answer 3

Ну ... во-первых, эта функция на самом деле никогда не выйдет. while(n > 0) в начале будет оставаться неизменным, потому что «n» никогда не изменяется в цикле. Так что это будет проблемой, если вы попытаетесь запустить его.

Но чтобы ответить на ваши вопросы:

m & 0x01 будет в основном проверить, если «т» является нечетным числом.Он делает это, выполняя побитную операцию между m и 0x01. Значение 0x01 является шестнадцатеричным представлением значения 1. Выполнение операции & между ними приведет к тому, что каждый бит будет сравниваться друг с другом (в двоичном формате) и установить значение 1 тогда и только тогда, когда оба соответствующих бита имеют значение единицы. Для получения дополнительной информации см. Некоторые исследования по двоичным и шестнадцатеричным представлениям и побитовым операторам.

>> - это еще один побитовый оператор, который сдвигает все биты в значение на одно место. В десятичном мире это эквивалентно делению на 2. Так что эта строка вызывает разделение на m на два каждый раз, когда она попадает в эту строку кода. Существует зеркальный оператор << для смещения бит в противоположном направлении и приравнивается к умножению на 2 вместо.

Надеюсь, это поможет!