为什么一维奇偶校验log（n）的大O运行时？

Question

因此，我正在从该网站上阅读一些代码：http : //www.geeksforgeeks.org/write-ac-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（log（n）），其中n是您传入的整数的值。但是，这是使用O表示法的非常规方式。

更经常地，O表示法是以输入的大小为单位（表示输入所需的位数）表示的，在这种情况下，输入的大小为k = O（log2（n））和运行时间是O（k）。

（更准确地说，运行时间是？（s），其中s是在n中设置的位数，尽管假设位运算是O（1））。