c++11 - O（log n）中的c ++位集逻辑运算？

Question

根据这篇文章，对位集执行按位运算的性能是 O(n)，我如何使它成为 O(log n)。谢谢。

Answer 1

答案是你没有。

假设您有一组n大小。让我们看一下 xor 运算符^。它显然必须查看两个操作数中的每一位，因此它会进行2n查找。这导致复杂度为O(n)。

您可以使用汇编指令，例如一次执行 32 位，因此操作数为(n+31)/32，但这并不会改变复杂性为O(n)。在计算所有复杂性之后，n趋向于无穷大并且忽略常数因素。