c - 分析这个算法(big-o)

Question

问题

这个算法在做什么？ 0x01代表什么？内部 while 循环中的 m = m >> 1 是什么意思？这个big-O算法是什么？

while(n>0)
{
     m = n;
     while(m)
     {
          if(m & 0x01)
          {
                c++;
          }
          m = m >> 1;
     }
}

尝试

1. 通过查看@算法，我了解到m右移了一位。
   (例如，如果 m = 1010，m >> 1 = 0101。这样正确吗？)

2. 因为有一个嵌套的 while 循环，并且因为每个 while 迭代 n 次，所以我猜测这个算法是 O(n^2)。对吗？

Answer 1

这个算法在做什么？ 对于 n 的值，将 n 中的位数添加到 c.

0x01 表示值 1。它被用作位掩码来检查 m 的最低位是否打开。如果是，则它递增 c。这是位计数部分。然后，m 被右移一次以将下一位向下移动到 LSB(最低有效位)的位置。 while(m) 将在 m 等于 0 时停止；也就是说，当 m 没有更多位时。

算法的复杂性取决于您使用 n 做什么。如果你递减它，那么你的算法是 O(n) 因为内部部分(while(m))是常量(因为有最大数量整数位，可能是 32)。

复杂度可能是 O(n * 32)，但由于常量是从 Big-Oh 表示法中取出的，所以您最终得到 O(n)。