对位集执行按位运算的性能

在 C++ 中，如果我对两个位集执行逻辑 OR（或 AND），例如：

bitset<1000000> b1, b2;
//some stuff
b1 |= b2;

这是在 O(n) 还是 O(1) 时间内发生的？为什么？

另外，这可以使用布尔数组在 O(1) 时间内完成吗？

Thanks.

它必须在 O(N) 时间内发生，因为给定处理器平台在任何给定时间块内可以处理的位数是有限的。换句话说，位组越大，每个操作花费的时间就越长，并且增加将与位组中的位数成线性关系。

使用数组也会遇到同样的问题bool类型。虽然每个单独的操作本身将花费 O(1) 时间，但 N 个对象的总时间将为 O(N)。