C#中的Bitvector32和位数组

Question

我想知道Bitvector32是否有操作时间为O(1)的位运算符。我目前使用的是大尺寸的BitArray，使用的是按位运算的And、Or和Not，它们在O(位数组的大小)中操作。

我在网上搜索了一下，但没有找到答案。希望这里的人能帮上忙！

Answer 1

• 将BitVector32转换为int是一个O(1)操作。对BitVector32进行(reference)
• Converting是一个O(1)操作。对整数进行逐位运算是一种O(1)运算。

因此，

var vectorAnd = new BitVector32(vector1.Data & vector2.Data);
var vectorOr = new BitVector32(vector1.Data | vector2.Data);
var vectorNot = new BitVector32(~vector1.Data);

都是O(1)运算。

Answer 2

假设BitVector32始终是32位的，那么没有可变的大小-那么如何用数据的大小来表示任何操作呢？

就我个人而言，我从来没有发现BitVector32是一种非常令人愉快的类型-我通常只会坚持使用UInt32来表示32位，并使用普通的&、|等运算符。

如果您正在考虑用一堆BitVector32值替换您的BitArray，那么最终的结果仍然是每个操作都是O(n)。从根本上说，这是很难避免的，除非你实际存储原始值和操作，推迟操作的实际应用-这将会复杂得多，只有当你只访问一小部分结果时，才会让事情变得更好。