Bitmask and Dynamic Programming

Bit manipulation is a crucial aspect of computer programming and one of the most powerful tools for bit manipulation is bitmasks.

Let's first understand what a bit is. A bit is a binary digit. It's the smallest piece of data in a computer and can be only either 0 or 1.

Binary Numbers

A binary number is a number expressed with a bunch of bits, where each bit is either 0 or 1 like described earlier. The integer types we use in programming languages are actually stored as binary numbers. Here is how binary numbers convert to decimal numbers:

You can check that in python:

>>> bin(21)
'0b10101'

Note that 0b means it's a binary number. The leading 0s are omitted and that's why we have 10101 instead of 010101.

Bitwise Operations

Bitwise operations are operations that work on individual bits of a number. Here are the primary bitwise operations that you'll use and encounter a lot in algorithmic problem solving.

Bitwise AND (&)

Given two integers x and y, the expression x & y is evaluated by doing the following:

First write the two integers in binary, in each column look at the bit in x and y, if both bits are 1, then the respective resulting bit will also be 1. Otherwise, if any bit in that column is 0, then the respective resulting bit will be 0.

This intermediate operation can be thought of as the boolean operator && and functions the same way.

Example

21 & 37 = 5

  0 1 0 1 0 1
& 1 0 0 1 0 1
=============
  0 0 0 1 0 1

Bitwise OR (|)

Given two integers x and y, the expression x | y is evaluated by doing the following:

First write the two integers in binary, in each column look at the bit in x and y, if any bit is 1, then the respective resulting bit will also be 1. Otherwise, if both bits in that column are 0, then the respective resulting bit will be 0.

This intermediate operation can be thought of as the boolean operator || and functions the same way.

Example

21 | 37 = 53

  0 1 0 1 0 1
| 1 0 0 1 0 1
=============
  1 1 0 1 0 1

Bitwise XOR (^)

Given two integers x and y, the expression x ^ y (not to be confused with exponents) is evaluated by doing the following:

First write the two integers in binary, in each column look at the bit in x and y, if the two bits are the same, then the respective resulting bit will be 0. Otherwise, if the two bits in that column are different, then the respective resulting bit will be 1.

This operation is also called the "exclusive or" operation.

Example

21 ^ 37 = 24

  0 1 0 1 0 1
^ 1 0 0 1 0 1
=============
  1 1 0 0 0 0

Notice that the 3 operations AND(&), OR(|), and XOR(^) are commutative. This means that the order of elements doesn't matter (i.e. x & y == y & x)

Bitwise Shifts (<< and >>)

Given two integers x and y, the expression x << y (bitwise left shift) is evaluated by doing the following:

Take the integer x and write it in binary and move all the 1 bits to the left y spaces.

This operation essentially takes the integer x and multiplies it by 2 exactly y times.

Example

21 << 2 = 84

   0 0 1 0 1 0 1
<<             2
================
   1 0 1 0 1 0 0

Similarly, the expression x >> y (bitwise right shift) is evaluated by doing the following:

Take the integer x, write it in binary, and move all the 1 bits to the right y spaces.

Notice that it might be possible for some bits to "disappear" if you move it past the "ones" bit.

In this case, we'll let them disappear.

It may be helpful to think of this operation as taking the integer x, and dividing it by 2 exactly y times. Here, the division is floor division, meaning we discard any remainders.

Example

21 >> 3 = 2

   0 0 1 0 1 0 1
>>             3
================
   0 0 0 0 0 1 0

Bitmask

Now, finally, what's a mask? We can construct a binary number such that a certain digit is set to 1 and other digits are all set to 0. This creates a "mask" that when we AND it to another binary it "turns off" (set to 0) all digits except the 1 digit in the mask.

We will see how we can use this to generate all subsets of an array in the next section.