c - Why is the big O runtime of 1D parity checking log(n)?

Question

So I am reading some code from this website: http://www.geeksforgeeks.org/write-a-c-program-to-find-the-parity-of-an-unsigned-integer/

And it shows how to determine whether a number has even or odd parity. However, I don't understand why the runtime efficiency is log(n). Here is the code for reference:

# 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(log(n)) です。ここで、nは渡した整数の値です。ただし、これは O 表記を使用する型にはまらない方法です。

多くの場合、O 表記はビット単位の入力のサイズ(入力を表すのに必要なビット数) で表されます。この場合、入力のサイズは k=O(log2(n)) であり、実行時間はは O(k) です。

(さらに正確には、ランタイムは Θ(s) です。ここで、s は n に設定されたビット数ですが、ビット操作が O(1) であると仮定しています)。

Answer 2

これを参照してくださいここで質問

ご覧のように、これを使用して 1 をカウントしません。ループは、n のバイナリ表現で 1 (1) (p としましょう) であるビットの数を正確に実行します。

したがって、複雑さは Θ(p) です。

n を表すために使用されるビットの最大数は log2(n) であるため、上限の漸近的境界 ID O(log2(n)) です。