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

Question

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

Answer 1

答案是你没有。

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

您可以使用汇编指令，例如一次执行 32 位，因此操作次数为(n+31)/32，但这不会改变复杂度为O(n)。毕竟复杂性是n针对无穷大计算的，常数因素被忽略。