CODEWITHSUNDEEP
algorithmlanguage-agnosticbit-manipulation
roulette01
roulette01

Reputation: 2462

How to iterate over subsets of a bitwise mask?

I have a bitwise mask represented as an integer. The mask and integer is limited to 32-bit integers.

I am interested in examining all subsets of the set bits of a given mask/integer, but I don't know of a good way to quickly find these subsets.

The solution that I've been using is

for(int j = 1; j <= mask; ++j)
{
  if(j & mask != 0)
  {
    // j is a valid subset of mask
  }
}

But this requires looping from j = 1 to mask, and I think there should be a faster solution than this.

Is there a faster solution than this?

My followup question is if I want to constrain the subset to be of a fixed size (i.e., a fixed number of set bits), is there a simple way to do that as well?

Upvotes: 0

Views: 1999

Answers (3)

YoungForest
YoungForest

Reputation: 181

Iterate all the subset of state in C++:

for (int subset=state; subset>0; subset=(subset-1)&state) {}

This tip is usually used in Bit mask + dp question. The total time complexity is O(3^n) to iterate all the subset of all state, which is a great improvement from O(4^n) if using the code in this question.

Upvotes: 2

Matt Timmermans
Matt Timmermans

Reputation: 59144

Given x with a subset of the bits in mask, the next subset in order is ( (x|~mask) +1 ) & mask. This will wrap around to zero if x==mask.

I don't have a super fast way for subsets with a fixed number of bits.

Upvotes: 0

potter1024
potter1024

Reputation: 205

For a bitmask of length n the maximum number of subsets of set bits can be 2^n - 1. Hence we have to traverse over all the subsets if you want to examine them, and therefore the best complexity will be O(mask). The code cannot be improved further.

Ps: If you want to count the total number of subsets, then it can be solved using dynamic programming with much better time complexity.

Upvotes: 1

Related Questions