C：在 O(1) 中将整数的第 i 位设置为 1

Question

现在，我知道设置数字的第 i 位的方法是使用移位运算符移动 1 直到达到所需的位，然后将其与数字进行或。但是这个过程是 O(length of number) 因为把一个数移动到第 i 个位置就像遍历到那里，对吧？如有不妥请指正

这是我的代码：

x = x| (1<<i)

有没有办法在 O(1) 中做到这一点？换句话说，如何直接访问数字中的位？我在考虑数组索引。

Answer 1

正如其他人指出的那样，n |= 1 << i 是 而不是 O(n)。这是因为大多数 CPU 中的位移位操作是一条指令，而我目前熟悉的指令需要一个或两个 IIRC 周期。

但是，如果您在 C 代码中引入循环，那么这当然是 O(n)，例如：

n = 1;
for(j = 0; j < i; ++j)
    n <<= 1;
x |= n;

对于用于在整数值中一般设置位的重构位设置，您可以执行如下操作：

typedef enum x_bits_e {
    x_bit1 = 1 << 0;
    x_bit2 = 1 << 1;
    x_bit3 = 1 << 2; 
     // and so on
};

int16_t set_bit_in_x(int16 x, x_bits_e i)
{ 
    return x | i;
}

Answer 2

将 1 移位 k 位是在硬件中完成的。在粗略简化的级别上，n 位 CPU 具有 n 寄存器，表示在每个方向上移动 0、1、2、...、n-1 位的数字。当执行移位操作时，CPU根据移位的个数加载一个寄存器k中的数，并在下一个循环中读取输出。这使得位移成为 O(1) 操作。

This Q&A 有一张图解释了使用多路复用器的现代 CPU 的 O(1) "magic" 背后的硬件。

C：在 O(1) 中将整数的第 i 位设置为 1

C: Setting the i'th bit of an integer to 1 in O(1)

c

bit-manipulation

bit

bitwise-operators

time-complexity