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 Operators

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.

111 & 101 = 101
101 & 100 = 100
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.

101 | 100 = 101
011 | 100 = 111
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)

101 ^ 111 = 010
1011 ^ 0100 = 1111
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.

~(1011) = 0100
~(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)

1 << 5 = 100000
(1 << 5) - 1 = 11111
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)

1101101 >> 2 = 11011
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 2², 2⁵, and 2⁸ digits set to 1.

1. Obtaining Empty Sets and Full Sets

Find a pizza that does not have any toppings, and a pizza that is full of toppings.

int emptyPizza = 0;
int fullPizza = (1 << 10) - 1;

2. 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);
// or simply
a |= (1 << n);

3. Check Whether Element is Included

Check if the pizza a has the nth number of toppings (where 0 <= n < 10)

if (a & (1 << n)) {
    cout << "Pepperoni is included !!!" << endl;
}

Note that (a & (1 << n)) returns 0 or (1 << n).

4. Delete the Element

You want to subtract the nth topping from pizza a (where 0 <= n < 10)

a = a & ~(1 << n);
// or simply
a &= ~(1 << n);

5. 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);
// or simply
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

7. Find the Least Significant Bit

Find out what is the smallest number of toppings in pizza a

int leastSignificantTopping = a & -a;

Example: 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 (2³)

8. Clearing the Minimum Bit

Topping minus the number of toppings in pizza a

int removedToppings = a & (a - 1);

Example: When 10110 = a

10110 & 10101 = 10100