Bit mask of bit operation

Use bit mask to realize set

Operation set is the most important application of bit mask . In this application ,N Bit integer variables indicate that you can have 0 To A-l Set of integer elements . To judge an element i Is included in the collection , Just look at the representation $2^i$ Whether the bit of has been turned on . for example , Can have 6 Collection of elements {1,4,5,6,7,9} The whole number of is 754 Shown by the following 、
21+24+25+26+27+29=101110010 = 754

Pizza shop example
Suppose a pizza shop allows customers to choose their own ingredients , Now I want to write a ordering system for this store . This pizza shop has 0 To 19 This is the number one 20 Ingredients , You can choose to add / Don't add . that ,1 The message of a pizza is 20 Collection of elements , So it can be represented by a bit mask . Of course , You can also use a size of 20 An array of Boolean types . however , Using bit mask can improve the speed of set operation through a variety of bit operations .

Find empty sets and compact sets

An empty set is 0 了 . Compact set

int fullPizza = (1<<20) - 1

take 1<< 20 Expressed in binary form , It's just one. 1 And noodles 20 individual 0 The integer of . Subtract one , You can get 20 Bits are turned on （1） The numerical

Additive elements

toppings |= (1<<p);

take 1 Move to the left p You get the first p Bit open integer

Confirm whether the element is included

if( toppings & (1<<p)) cout<<" in it!"<<endl;

& That only toppings Of the i Only when the bit is turned on can it be true

Remove elements

toppings &= ~(1<<p);

Switch elements

It turns out to be 0 becomes 1, yes 1 becomes 0

toppings ^= (1<<p);

Operation on two sets

int added = (a|b); //a and b A collection of 
int intersection = (a&b);// a and b Intersection 
int removed = (a&~b); //  from a subtract b The difference between the set 
int toggled = (a^b); //  Only be  a and b  A set in   Contains a collection of elements .

Find the smallest element

That is to say, there are several current low positions 0？

int firstTopping = (toppings & -topping);

Delete the smallest element

toppings &= (topping - 1);

Traversing subsets

for(int subset = pizza; subset;subset = ((subset-1)&pizza)){
    
// subset  yes pizza Subset 
}