查找给定数字是否为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的幂,则总共设置一个比特,减去1将使该比特为零,并将所有比特设置为右边的1.

它遵循,num并且num - 1 不能共享任何设置位.因此,num & (num - 1)评估为0.

如果num是不为二的幂(和不为零),也有至少设置两个比特.当减去一个时,只改变最右边的设置位,然后改变它的右边,接下来,其他的不会受到影响.

因此,num并num - 1分享最多一个设置的比特.我们得出结论,num & (num - 1)对于num非零而不是2的幂,不能评估为零.

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

复杂性:在常规计算机上,所有二进制操作都在恒定时间内发生.因为有固定数量的常量时间操作,所以整个函数将在恒定时间内返回:O(1).

当您n对该功能执行调用时,每次调用它时都会执行恒定的工作量.当n双打,工作量增加一倍.因此,该案件的复杂性是O(n).