algorithm - 查找给定数字是否为 2 的幂的时间复杂度

Question

我正在尝试计算以下函数返回的时间复杂度-

int isPowerof2(unsigned int num)
{
     if(((~num)&1) == 1)
          return 1;
      return 0;
}

我认为它应该是 O(1) 但我不确定否定的复杂性。有人可以帮助我了解如何确定这方面的复杂性。谢谢！

编辑-如果在单个数字的情况下将其视为 n 个输入并且函数检查 2 的幂，那么在这种情况下的复杂性是多少

Answer 1

以二进制表示的 2 的幂恰好设置了一个位，所有其他位都为零。

减一将反转所有位，包括最右边的一位：

110101100 - 1=> 110101011 (in the case of zero, all bits get inverted)

我们假设num & (num - 1)当且仅当num是 2 的幂时，它的计算结果为零。

如果num实际上是 2 的幂，则总共设置了一个位，减去一个将使该位变为 0，并将其右侧的所有位设置为 1。

因此，num不能num - 1 共享任何设置位。因此，num & (num - 1)评估为 0。

如果num不是2 的幂（并且不是零），则至少设置了两个位。当减去一个时，只有最右边的设置位被改变，而那些在它右边的，那么其他的将不会受到影响。

因此，num最多num - 1共享一个设置位。我们得出结论，对于非零且不是 2 的幂，num & (num - 1)不能评估为零。num

因此正确的检查是：num && !(num & (num - 1))

复杂性：在普通计算机上，所有二进制操作都在恒定时间内发生。因为有固定数量的恒定时间操作，所以整个函数会以恒定时间返回：O(1).

当您执行n对该函数的调用时，您每次调用它时都会执行固定时间量的工作。当n翻倍时，工作量翻倍。由此可见，这种情况的复杂性是O(n)。

Answer 2

现代处理器以恒定数量的时钟对机器字大小的整数进行基本的算术和逻辑运算，而与这些整数的值无关。因此，函数中的所有这些操作都是 O(1)，并且由于操作的数量是固定的，因此整个函数是 O(1)。

顺便说一句，该函数不会判断给定数字是否是 2 的幂。它会判断它是否是 2 的倍数，因为它只查看 的最低有效位num。

对 2 的幂的正确检查是这样的：

int isPowerof2(unsigned int num)
{
  return (num != 0) && ((num & (num - 1) == 0);
}