10. Bitmask
-
Basic knowledge
Computers represent all integer variables in binary numbers.
At this time, one digit of binary number is expressed as bit.
For example, an unsigned integer from 0 to 255 can be represented with 8 bits.
0 = 00000000
255 = 11111111
- For unsigned N-bit integers,
2 ⁰ is the least significant bit,
2 ^ (N-1) is called the most significant bit.
The value of a particular bit may be 0 or 1,
1: “On”
0: “off”
Bitwise operator
The following operations are possible for values where all digits are bits (0 or 1).
- AND operation (symbol: a & b): only 1 if both are 1, even if only one of them is 0, the result is 0.
ex) 111 & amp; 101 = 101
ex) 101 & amp; 100 = 100
ex) 001 & 100 = 0 - OR operation (symbol: a | b): only 0 if both are 0, only one of them results in 1 if the value is 1.
ex) 101 | 100 = 101
ex) 011 | 100 = 111
ex) 1000 | 0101 = 1101 - XOR operation (symbol: a ^ b): 0 if they are the same value (11 or 00) and 1 if they are different values (10 or 01)
ex) 101 | 111 = 010
ex) 1011 | 0100 = 1111
ex) 1011 | 1100 = 0111 - NOT operation (symbol: ~ a): This operation applies to a single bit value, not an operation on two bit values. Invert each digit to the opposite value. That is, when the value is 0, the value is changed to 1, and when the value is 1, the value is changed to 0.
ex) to (1011) = 0100
ex) to (0011) = 1100 - LEFT SHIFT operation (symbol: a << b): Pushes the bits of all the digits of the value a to the left by b times. (With 0 on the right)
ex) 1 << 5 = 100000
ex) (1 << 5) — 1 = 11111
ex) 1011 << 2 = 101100 - RIGHT SHIFT operation (symbol: a >> b): Pushes the bits of all the digits of the value a to the right by b times. (With 0 on the left)
ex) 1101101 >> 2 = 11011
ex) 110010 >> 5 = 1
Playing with bits
The above is a computation that should be studied while studying logic or mathematics.
The problem is how to use bits effectively with these operations.
From now on, each digit of the 10-digit bit (0–9) will think about the addition of different toppings of the pizza,
Let’s take a look at the available methods, assuming that the pizza is represented by a 10-digit bit value.
In other words, the value of 0100100100 will be the pizza with 3 toppings due to the ²², ²⁵, and ²⁸ digits set to 1.
- Obtaining empty sets and full sets
= Find a pizza that does not have any toppings, and a pizza that is full of toppings.
Pizza without topping: int emptyPizza = 0
Pizza full of toppings: int fullPizza = (1 << 10) - 1 - Adding elements
= Add n toppings to pizza a (where 0 <= n <10)
If you want to change only a specific value from 0 to 1 for the current pizza.
If you already have that topping, just keep it at 1.
a = a | (1 << n)
That is,
a | = (1 << n) - Check whether element is included
= Check if the pth a has the nth number of toppings (where 0 <= n <10)
Let's say the pepperoni topping number is n.
if (a & (1 << n)) cout << "Pepperoni is included !!!" << endl;
Note that the red part returns 0 or (1 << n). (True if true, or 1 if misunderstood) - Delete the element
= You want to subtract the nth topping from pizza a. (Where 0 & lt; = n & lt; 10)
a = a & ~ (1 << n)
In short
a & = ~ (1 << n) - Toggle the element
= Add the nth topping of pizza a if it does not exist, remove it if there is one.
a = a ^ (1 << n)
In short
a ^ = (1 << n) - 6. Other set operations
int added = (a | b); // Union
int intersection = (a & b) // intersection
int removed = (a & ~ b) // Difference set a — b
int toggled = (a ^ b) // A set of elements only in one of a and b (the union of a and b minus the intersection) - Find the least significant bit
= Find out what is the smallest number of toppings in pizza a
int leastSignificantTopping = a & -a
ex) Let’s say for example a five-digit number 40
-40 is (01100) as follows using the two’s complement arithmetic method.
10100 = 40
01011 + 1 = 01100 = (-40)
10100 & 01100 = 00100 (²³) - Clearing the minimum bit
= Topping minus the number of toppings in pizza a
int removedToppings = a & (a — 1)
ex) When 10110 = a,
10110 & amp; 10101 = 10100
