c - 为什么一维奇偶校验的大O运行时是log(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(log(n))，其中 n 是您传入的整数的值。但是，这是一种非常规的 O(log(n)) 使用方式符号。

更常见的是，O 表示法根据输入的大小 以位表示(表示输入所需的位数)，在这种情况下，输入的大小为 k= O(log2(n))，运行时间为 O(k)。

(更准确地说，运行时间是 Θ(s)，其中 s 是 n 中设置的位数，尽管假设位操作是 O(1))。