分析涉及按位运算和 2 的幂的算法？

Question

我编写了一个程序来计算给定输入数中 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;
}

我在算法分析方面遇到了一些困难。我知道我们正在尝试找出 Big-Oh、Big-Omega 或 Big-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) 等？

Answer 1

这是一个很好的算法示例，如果您对算法的作用有很好的直觉理解，而不是仅仅查看代码本身，就更容易推理它。

首先，i & (i - 1) 是做什么的？如果你取一个用二进制写成的数减一，它的效果是

清除最低有效 1 位，并且
将之后的所有位设置为 1。

例如，如果我们将二进制数 1001000 (72) 减一，我们得到 1000111 (71)。请注意最低有效的 1 位是如何被清除的，并且它下面的所有位都设置为 1。

当您将数字 i 与数字 i - 1 进行 AND 运算时会发生什么？好吧，i 和 i - 1 中最低有效 1 位以上的所有位都没有变化，但是 i 和 i - 1 在所有位置不一致，在至少 - i 中的重要 1 位。这意味着 i & (i - 1) 具有清除数字中最低 1 位的作用 i.

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

如您所述，要了解该算法的最佳和最坏情况行为，如果 n 是 2 的完美幂，则运行时间为 O(1)。这和这将要达到的一样好。对于最坏的情况，数字 n 可能全为 1 位，在这种情况下，数字 n 中将设置 Θ(log n) 1 位（因为在二进制中，数字 n 需要 Θ(log n ) 位写出)。因此，最坏情况下的运行时间为 Θ(log n).

综上所述，我们看到

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

分析涉及按位运算和 2 的幂的算法？

Analyzing an algorithm involving bitwise operations and powers of two?

c++

algorithm

bit-manipulation

big-o

time-complexity