### Ahnaf.Shahriar.Asif's blog

By Ahnaf.Shahriar.Asif, history, 3 years ago,

Recently, I learned Bitmask DP and used only a variable to see if some block was visited or not. But now I want to do it using std::bitset. Will it be more or less efficient than the first one ? If yes or no, why ? I'm just confused. I think bitset should be fine. and I want to use it because it is easy to use.What's your opinion ? thanks in advance.

• +16

 » 3 years ago, # |   -14 quite obviously, using a primitive data type like long will be more efficient. But the problem is, what if you want to represent a bitmask that has more than 64 bits?
•  » » 3 years ago, # ^ |   -6 :( . Yah . I think it is not possible using bitset :'(
•  » » 3 years ago, # ^ | ← Rev. 2 →   +29 quite obviously, using a primitive data type like long will be more efficient. Actually gcc's standard lib implementation is specialised for short bitset and uses one long instead of array of longs, so they may be close to the same (but of course, it may still be not true, I have not measured that)
 » 3 years ago, # |   +3 I think int is easier to use for bitmask dp because it is easier to store and loop through all possible states. The main use for bitset I have seen is when you have an O(n2) dp solution and are looking for an extra speed boost to squeeze it in the time limit. Definitely a cool trick that makes problem setters sad/apologetic when it works.
•  » » 2 years ago, # ^ |   -7 ok
 » 2 years ago, # | ← Rev. 2 →   +5 If an integer has enough bits it will most likely be at least as fast as a bitset. If you need more bits than that for a bitmask DP it's probably not going to work out anyway unless you're doing memoization where only a small number of states are actually needed. Bitsets are useful for quickly performing operations on a large number of bits, such as logical operations, counting set bits, and bitshifting. As far as I know they aren't very useful for bitmask DPs.