分析一个涉及位运算和二的幂次方的算法？

Question

分析一个涉及位运算和二的幂次方的算法？

c++algorithmbit-manipulationbig-otime-complexity

3

我写了一个程序，用于计算给定输入数字中最大的2的幂。例如，数字26中最大的2的幂是16，因为2⁴等于16。以下是算法：

uint power2( uint n )
{
   uint i = n;
   uint j = i & (i - 1);
   while( j != 0 )
   {
      i = j;
      j = i & (i - 1);
   }
   return i;
}

我在算法分析方面有些困难。我知道我们试图确定大写-Oh、大写-Omega或大写-Theta符号。为了分析一个算法，我们应该计算基本操作的数量吗？我的问题是我看到两行可能是基本操作。我看到while循环外面的一行uint j = i & (i - 1)，还有while循环里面的j = i & (i - 1)。我觉得while循环里面的那个肯定是基本操作，但是while循环外面的那个呢?

我另一个困难的部分是确定while循环体将执行多少次。例如，如果我们有一个for循环for(int i = 0; i < n; i++) {...}，我们知道这个循环将执行n次。或者在一个while循环while(i < n * n) {... i++}中，我们知道这个循环将运行n * n次。但对于这个while循环来说，它取决于输入。例如，如果你传入的数字恰好是2的幂，那么while循环就不会执行。但是，如果你传入一个非常大的数字，它将执行多次。老实说，我不知道它将执行多少次。这就是我想弄明白的东西。有人能帮我理解一下这个算法以及它运行的次数，比如O(n)或O(n^2)等吗？

- GenericUser01

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

这是一个很好的算法示例，当你对它正在做什么有一个良好的直观理解时，比仅仅查看代码本身更容易进行推理。

首先，i & (i - 1) 做了什么？如果你用二进制表示一个数字，并将其减一，它会产生以下效果：

清除最低有效位（least-significant 1 bit），并
将该位以下的所有位设置为1。

例如，如果我们取二进制数 1001000（72）并减去一，我们得到 1000111（71）。注意最低有效位被清除，并且该位以下的所有位都被设置为1。

当你用数字 i 和数字 i - 1 进行 AND 运算时会发生什么？那么，在两个数字 i 和 i - 1 中最低有效位之上的所有位保持不变，但是在 i 和 i-1 的最低有效位及其以下位置上的所有位都是不同的。这意味着，i & (i - 1) 的效果是清除数字 i 中的最低有效位。

那么让我们回到代码。请注意，每次 while 循环迭代都使用这种技术从数字 j 中清除一位。这意味着 while 循环的迭代次数与数字 n 中设置的1位数成正比。因此，如果我们用 b 表示在 n 中设置的1位数，则该算法的运行时间为 Θ(b)。

为了了解该算法的最佳和最坏情况行为，正如你所指出的，如果 n 是二的幂，则运行时间是 O(1)。这就是它能达到的最好状态。对于最坏情况，数字 n 可能是全1位，其中数字 n 中有 Θ(log n) 个1位（因为在二进制中，数字n需要 Θ(log n) 位来写出）。因此，最坏情况的运行时间为 Θ(log n)。

总之，我们看到：

最佳情况下，运行时间是 O(1)，
最坏情况下，运行时间为 Θ(log n)，且
确切的运行时间为 Θ(b)，其中 b 是 n 中设置的1位数。