使用位操作反转8位无符号整数的时间复杂度疑问

首先明确结论：你这个处理固定8位无符号整数的位反转算法，时间复杂度是O(1)。如果非要在你提到的O(N)和O(logN)里做区分，得先明确变量的定义：

• 你最初认为是O(N)，这里的N如果指的是「整数的位数」，但在你的场景里位数是固定的8——它是一个常数，不会随输入的数值大小变化而增长，所以不能算作O(N)（O(N)要求N是随输入规模增长的变量）。
• 要是把问题泛化到处理任意n位的整数：
  • 如果把「位数n」作为变量，那循环次数等于n，时间复杂度是O(n)；
  • 如果把「输入数值的大小N」作为变量，因为n位整数的最大值是2ⁿ-1，所以位数n = log₂(N) + 1，这时候循环次数和logN成正比，时间复杂度就是O(logN)。

回到你的具体场景：不管输入是9（00001001b）还是10（00001010b），循环都会固定执行8次，和输入数值的大小无关，所以是标准的常数时间复杂度O(1)。

举个对应C语言的代码例子更直观：

uint8_t reverse_bits(uint8_t num) {
    uint8_t result = 0;
    for (int i = 0; i < 8; i++) {
        // 取num的第i位，放到result的第7-i位
        result |= ((num >> i) & 1) << (7 - i);
    }
    return result;
}

这段代码里的循环次数固定是8，完全不依赖输入num的具体值，所以时间复杂度是O(1)。

内容的提问来源于stack exchange，提问作者Lokesh Waran