CODEWITHSUNDEEP
c++bitset
citizenCode
citizenCode

Reputation: 95

Performance of doing bitwise operations on bitsets

In C++ if I do a logical OR (or AND) on two bitsets, for example:

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

Does this happen in O(n) or O(1) time? Why?

Also, can this be accomplished using an array of bools in O(1) time?

Thanks.

Upvotes: 5

Views: 6035

Answers (3)

SinisterRainbow
SinisterRainbow

Reputation: 145

I think it needs to be made clear that Big O is a boundary - an asymptotic boundary (minimum time required cannot be less than the f(x)'s Big O., and in in thinking about it, it states the order of magnitude of the speed of a computation. So if you think about how an array works - if you can say I can do this operation all in one computation or so, or there's a known amount that is very small and much less than N, then it is constant. If you need to iterate in some manner (in this case you will see all the bits need to be checked, and there is no short cut for bitwise OR - therefore N bits need to be computed, and therefore it's O(n). [It's actually tighter boundary than that, but we're dealing with just Big O]. An array itself stores N-bits in it.

In fact, few things are really O(1) (index look ups at a known address using a pointer can be O(1) (if you already know what you are looking up). But, if you have M things that need to be looked up in constant time, then it is O(M) * O(1) = O(M).

This is a function of modern day computer - since most things are processed sequentially. (multi-core helps but doesn't come close to affecting big O notation yet). There is of course, the ability of the computer to process words in parallel, but even that is just a constant subtraction. O(n) / O(64) is still O(n).

Upvotes: 1

Adam Mihalcin
Adam Mihalcin

Reputation: 14478

It's impossible to perform a logical operation (e.g. OR or AND) on arbitrary arrays of flags in unit time. True Big-Oh analysis deals with runtime as the size of the data tends to infinity, and a Core i7 is never going to OR together a billion bits in the same time it takes to OR together two bit.

Upvotes: 1

Jason
Jason

Reputation: 32538

It has to happen in O(N) time since there is a finite number of bits that can be processed in any given chunk of time by a given processor platform. In other words, the larger the bit-set, the longer the amount of time each operation will take, and the increase will be linear with respect to the number of bits in the bitset.

You also end up with the same problem using the array of bool types. While each individual operation itself will take O(1) time, the total amount of time for N objects will be O(N).

Upvotes: 6

Related Questions