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

Question

现在,我知道设置数字的第i位的方法是使用移位运算符移位1直到达到所需位,然后只是或者数字.但是这个过程是O(数字的长度),因为将数字移到第i个位置就像遍历到那里,对吧？如果我错了,请纠正我.

这是我的代码:

x = x| (1<<i)

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

Answer 1

换档1由k位在硬件完成.在非常简化的级别上,n位CPU具有n表示在每个方向上移位0,1,2,...,n-1位的数字的寄存器.当执行移位操作时,CPU k根据移位次数将数字加载到寄存器中,并在下一个周期中读取输出.这使得位移O(1)操作.

这个Q&A有一个图解释了使用多路复用器的现代CPU的O(1)"魔力"背后的硬件.