c - 为什么一维奇偶校验 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)）。

Answer 2

在这里看到这个所以问题

正如你所看到的，我们使用这个来计算 1 的数目，循环将准确地运行 n 的二进制表示中为一（1）（比如说 p）的位数。

因此复杂度是 Θ(p)。

并且由于用于表示 n 的最大位数是 log2(n) ，因此上渐近界 id O(log2(n))。