Menu
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.
831
As bitset stores the same information in compressed manner the operation on bitset are faster than that of array and vector.
Bitwise operations are incredibly simple and thus usually faster than arithmetic operations. For example to get the green portion of an rgb value, the arithmetic approach is (rgb / 256) % 256 . With bitwise operations you would do something as (rgb >> 8) & 0xFF .
Rhetorical question: Why std::bitset is written in that inefficacy way? Answer: It is not. If i > 64 then bit set will be zero and in case of unsigned we have UB.
Yes, Bitwise operations are alot faster than any arithmetic operations because these operations are performed directly on the bits that is 0 and 1. In this operation we will get the output Odd.
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).
131
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
