询问下述Power Of Two代码的时间复杂度及非常数时间下的优化方案

首先咱们来拆解你给出的这段判断是否为2的幂的代码：

static bool powerOfTwo(double number) { 
    double log = Math.Log(number, 2); 
    double pow = Math.Pow(2, Math.Round(log)); 
    return pow == number; 
}

时间复杂度分析 #

这段代码的核心依赖Math.Log和Math.Pow这两个数学库函数。这些函数的底层实现不是常数时间O(1)——它们通常采用迭代逼近算法（比如泰勒展开、牛顿迭代法）来计算对数和幂，迭代次数会根据所需的精度要求变化，实际时间复杂度更接近O(log n)（或者说取决于输入值的大小和浮点精度需求）。

另外，除了时间复杂度的问题，这段代码还有一个致命的隐患：浮点数精度误差。比如当number是非常大的2的幂（比如2^{53之后），double类型无法精确表示所有整数，这时候`Math.Log`计算出的结果会有偏差，`Math.Round`后再反推的幂值就会和原数不相等，导致判断错误；还有像0.5（2}-1）这类小数，也可能因为浮点精度问题出现误判。

更优解决方案 #

如果你的场景是判断整数类型的2的幂（这也是最常见的场景），我们可以利用二进制位运算实现真正的O(1)常数时间判断：

方案1：针对正整数的位运算优化 #

对于正整数n，2的幂的二进制表示只有一个1，比如2(10)、4(100)、8(1000)等。当我们用n和n-1做按位与运算时，结果会是0（因为n-1会把唯一的1变成0，后面的位全变成1，按位与后全0）。代码如下：

static bool IsPowerOfTwo(int n) {
    // 排除0和负数，因为2的幂都是正整数
    return n > 0 && (n & (n - 1)) == 0;
}

方案2：兼容double类型的严谨判断 #

如果必须支持double类型（比如需要判断像0.5、0.25这类2的负次幂），可以先验证输入是否是2的整数次幂，同时处理浮点数的精度问题：

static bool IsPowerOfTwo(double number) {
    if (number <= 0) return false;
    
    // 用Math.ScaleB来获取指数（double的二进制表示中指数部分对应2的幂次）
    int exponent;
    double mantissa = Math.ScaleB(number, -Math.GetExponent(number));
    // 当mantissa是1.0时，说明原数是2的整数次幂（因为double的尾数部分是1.xxxx，只有xxxx全为0时mantissa是1）
    return mantissa == 1.0;
}

这个方案利用了double的IEEE 754二进制表示特性，Math.GetExponent可以直接获取指数部分，Math.ScaleB用来归一化尾数，整个过程是常数时间O(1)，而且避免了对数和幂运算带来的精度问题。

内容的提问来源于stack exchange，提问作者Muhammad Ali