c - C中位反转函数的时间复杂度

Question

#include <stdio.h>

unsigned int reverseBits(unsigned int num)
{
    unsigned int reverse_num = 0;
    for(int i = 0; i < sizeof(unsigned int) * 8; ++i)
    {   
        reverse_num = (reverse_num | (num & 1));
        num = num >> 1;
        if(i != (sizeof(unsigned int) * 8) - 1)
            reverse_num = reverse_num << 1;
    }   
    return reverse_num;
}

int main()
{
    unsigned int num = 0;
    scanf("%u", &num);
    printf("bit reverse of %u is %u\n", num, reverseBits(num));
    return 0;
}

这个位反转函数的时间复杂度是多少，如果我们将输入大小改为uint_8/uint_16/uint64_t，for循环运行输入大小* 8次。此函数针对 n 个输入在恒定时间内运行。那么这个函数在大“O”符号中的时间复杂度是多少？

Answer 1

O(n)，n 位。

对于uint_8，算法分8步运行。
对于 uint_16，算法分 16 步运行。

等等

---

我不是专家，但一些指令集可能有一个周期位反转(使用 __asm__)，所以你可以在 O(n) 中运行 n 字节;快八倍。如果您使用 -O3，一些编译器可能会自动执行此操作。