Алгоритм подсчета битов (Брайан Керниган) в целочисленной временной сложности

Может кто-нибудь объяснить, почему алгоритм Брайана Кернигана берет O (log N) для подсчета битов (1s) в целое число. Простая реализация этого алгоритма ниже (в JAVA)

int count_set_bits(int n){
    int count = 0;
    while(n != 0){
        n &= (n-1);
        count++;
    }
    return count;
}

Я понимаю, как это работает, очищая крайний правый бит один за другим, пока он не станет 0, но я просто не знаю, как мы получаем O (log N).

Ответы

Ответ 1

Этот алгоритм проходит через столько итераций, сколько есть битов. Поэтому, если у нас есть 32-битное слово с набором только высоких бит, он будет проходить один раз через цикл. В худшем случае он будет проходить один раз за бит. Целое число n имеет бит log(n), поэтому наихудший случай - O(log(n)). Здесь ваш код аннотируется с важными битами (каламбур):

  int count_set_bits(int n){
        int count = 0; // count accumulates the total bits set 
        while(n != 0){
            n &= (n-1); // clear the least significant bit set
            count++;
        }
  }

Ответ 2

Есть пол (lg (N)) + 1 значащий бит в N - логарифм базы-2. Число 1 бит в n не более того. Таким образом, время будет иметь асимптотическую верхнюю грань O (lg (N)) = O (log (N)).

Ответ 3

Этот вопрос действительно о значении N в большой нотации O, а не сложности алгоритма.

N означает размер данных. Но в случае, когда "данные" - это один номер, вам нужно определить, что вы понимаете как размер данных. Значение числа или длины его представления.

IMO алгоритм O (N). Поскольку в этой задаче подсчета 1 в двоичном представлении ИМО соответствующий размер данных - это длина представления числа, а не значение, то есть длина битового потока. И очевидным худшим случаем является то, что все 1 принимают N итераций.

Но если вы рассматриваете значение N как размер данных, это представление имеет длину журнала (N), поэтому вы можете сказать это O (log (N))

PS Также большое примечание O имеет смысл только в том случае, если вы обобщаете алгоритм для произвольно высокого Ns. В этом коде N ограничено размером int, поэтому вы можете сказать это O (1), так как будет не более 64 циклов итераций (для 64-битных ints)