Почему большое время автономной работы 1-го журнала проверки четности (n)?

Question

Так что я читаю код с этого сайта: http://www.geeksforgeeks.org/write-a-c-program-to-find-the-parity-of-an-unsigned-integer/

И это показывает, как определить, имеет ли число четную или нечетную четность. Однако я не понимаю, почему эффективность выполнения - log (n). Вот код для справки:.

# include <stdio.h> 
# define bool int 

/* Function to get parity of number n. It returns 1 
    if n has odd parity, and returns 0 if n has even 
    parity */ 
bool getParity(unsigned int n) 
{ 
    bool parity = 0; 
    while (n) 
    { 
     parity = !parity; 
     n  = n & (n - 1); 
    }   
    return parity; 
} 

Answer 1

Эффективность выполнения является O (журнал (п)), где n является значения целого числа вы передаете в Тем не менее, это нетрадиционный способ использования O обозначений ,

Чаще всего обозначение O выражается в виде размера ввода в битах (число бит, необходимое для представления ввода), и в этом случае размер ввода равен k = 0 (log2 (n)), а время выполнения - O (k).

(Более точно, время выполнения равно Θ (s), где s - количество бит, установленных в n, хотя предполагается, что операции бит - это O (1)).

Answer 2

Смотреть это Так question here

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

Таким образом, сложность Θ (p).

, а максимальное количество битов, используемых для представления n, является log2 (n), поэтому верхняя асимптотическая граница id O (log2 (n)).