Bitvector32 and Bitarray in C#

Question

I wanted to know whether there are bitwise operators for Bitvector32 that operate in O(1) time. I am currently using BitArray of large sizes and using Bitwise And,Or and Not which operate in O(size of bitarray).

I searched the internet for this but could not find an answer. Hope people here can help!

Answer 1

• Converting a BitVector32 to an int is an O(1) operation. (reference)
• Converting an int to a BitVector32 is an O(1) operation. (reference)
• Executing a bitwise operation on an int is an O(1) operation.

Thus,

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

are all O(1) operations.

Answer 2

Given that a BitVector32 is always exactly 32 bits, there's no varying size to speak of - so how could any operation be expressed in terms of the size of the data?

Personally I've never found BitVector32 a terribly pleasant type - I would usually probably just stick to a UInt32 to represent 32 bits, and use the normal &, | etc operators.

If you're thinking of replacing your BitArray with a bunch of BitVector32 values, that's still going to end up making each operation O(n). Fundamentally it's hard to avoid that, unless you actually store original values and operations, deferring the actual application of the operation - which will be much more complicated, and only end up making things better if you only access a small proportion of the results.