1

问题

这个算法在做什么？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)。那是对的吗？

4

3 回答 3

0

内部循环正在计算 m 中“1”位的数量。它的成本是 O(log m)，因为每次迭代它都会将 m 的值减半，直到它达到 0。

（如果你认为 m 是一个固定大小的整数，比如 32 位，那么你可以说内部循环是 O(1)，因为它总是最多进行 32 次操作，这是一个常数）

正如一些人所指出的，外循环永远不会结束，因为 n 永远不会改变。（除非 n 为 0）。

所以总的来说这段代码是 O(infinity)，它永远不会完成。

于 2013-07-26T22:50:08.410 回答
0

What is this algorithm doing? 对于 的值n，将 in 上的位数n添加到c。

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

算法的复杂性取决于你在做什么n。如果您要递减它，那么您的算法是O(n)因为内部部分 (the while(m)) 是恒定的（因为整数中有最大位数，可能是 32）。

复杂性可能是O(n * 32)，但由于常量是从 Big-Oh 表示法中取出的，因此您最终会得到O(n).

于 2013-07-26T22:52:43.090 回答
0

嗯……一方面，这个函数实际上永远不会退出。at start将while( n > 0 )始终保持为真，因为 'n' 永远不会在循环内修改。因此，如果您尝试运行它，那将是一个问题。

但要回答你的问题：

基本上会m & 0x01检查'm'是否是奇数。它通过在m和之间进行按位运算来做到这一点0x01。value0x01是 value 的十六进制表示1。在它们之间进行&操作将导致每个位相互比较（以二进制形式），并且1当且仅当两个匹配位的值都为 1 时才设置为。有关更多信息，请对二进制和十六进制表示以及按位运算符进行一些研究。

这>>是另一个按位运算符，它将一个值中的所有位移动一个位置。在十进制世界中，这相当于除以 2。因此，m每次到达该行代码时，该行都会导致 的值除以 2。有一个镜像运算符<<用于向相反方向移动位，相当于乘以 2。

希望这可以帮助！

于 2013-07-26T22:53:19.560 回答