Bit Flags

For the computer, every number is a series of bits: ones and zeroes. A set of "bit flags" is a series of numbers that we can compare to each other.

Say I have coins with the following values:

• Coin A has a value of 1
• Coin B has a value of 2
• Coin C has a value of 4

If I ask you to take one, two, or three coins without me looking, I can guess which you have by asking you the total number:

• If you have 1, 2, or 4, you took one coin
• If you have 3, you took A and B
• If you have 5, you took A and C
• If you have 6, you took B and C
• If you have 7, you took all three coins

By using the mathematical property of powers of 2, we can combine these numbers in any way and still have all the information they contain.

Where would you use bit flags?

Here's an example of bit flags that determine which powers a hero has access to:

const FLIGHT = 1
const TELEPATHY = 2
const HEALING = 4

var powers := 0

A hero may have zero, one, two, or all three powers. We can represent this with a single number, for example, 5 for a hero with flight and healing.

How does this work? You notice how each number is a power of 2. Thanks to this trick, we can combine these numbers in any way and still have all the information. Let's look at examples:

• FLIGHT and HEALING are 1 and 4. Adding them together is 5.
• FLIGHT and TELEPATHY are 1 and 2. Adding them together is 3.
• TELEPATHY and HEALING are 2 and 4. Adding them together is 6.
• FLIGHT, TELEPATHY, and HEALING are 1, 2, and 4. Adding them together is 7.

You notice no combination produces the same number; this means that if powers is equal to 5, we know for sure the hero has flight and healing. This works because of the mathematical property of powers of 2: their combinations are unique and don't overlap.

Wouldn't it work with sequential numbers?

Let's try!

const FLIGHT = 1
const TELEPATHY = 2
const HEALING = 3

• FLIGHT and HEALING are 1 and 3. Adding them together is 4.
• FLIGHT and TELEPATHY are 1 and 2. Adding them together is 3... Uh oh! This is the same as HEALING. With this, we can't distinguish between a hero with flight and telepathy or a hero with healing.

Bit flags express a lot with a little

Bit flags give us a good way to pass multiple booleans.

Consider the function below:

const PEPPERONI = 1
const MUSHROOMS = 2
const ONIONS = 4
const SAUSAGE = 8
const BACON = 16
const EXTRA_CHEESE = 32
const BLACK_OLIVES = 64

func make_pizza(ingredients_flags: int) -> bool:
    if ingredients_flags & PEPPERONI:
        print("Pepperoni")
    if ingredients_flags & MUSHROOMS:
        print("Mushrooms")
    # ...

Contrast with:

func order_pizza(
  pepperoni: bool,
  mushrooms: bool,
  onions: bool,
  sausage: bool,
  bacon: bool,
  extra_cheese: bool,
  black_olives: bool) -> bool:
    if pepperoni:
        print("Pepperoni")
    if mushrooms:
        print("Mushrooms")
    # ...

Bit flags encode many booleans in a compact variable. If you wonder what this & business is, it's a bitwise AND operation, and I'll explain it below.

Performance

In computing, bit flags have another great advantage: computers can operate on bits very fast, so comparing, adding, or removing bit flags is very efficient. The name "bit flags" comes from the way bits can be set or unset to represent the flags.

Let's go back to our example, and let's write the binary form of the numbers in a comment next to each. Before, let me remind you of how to write the first few numbers in binary:

| number | binary | | ------ | ------ | | 0 | 0000 | | 1 | 0001 | | 2 | 0010 | | 3 | 0011 | | 4 | 0100 | | 5 | 0101 | | 6 | 0110 | | 7 | 0111 | | 8 | 1000 |

Ok, you can refer to this table to read the below.

const FLIGHT = 1    # 0001
const TELEPATHY = 2 # 0010
const HEALING = 4   # 0100

Let's set the bits from FLIGHT and TELEPATHY to represent a hero with flight and telepathy:

| power | number | binary | | ---------- | ------ | ------ | | FLIGHT | 1 | 0001 | | TELEPATHY | 2 | 0010 | | result | 3 | 0011 |

The computer doesn't need to calculate 1 + 2. All it needs is to flip the bits for all the 1s in both numbers. The result is indeed 0011, which represents 3 in binary.

Let's try this again with FLIGHT and HEALING:

| power | number | binary | | ---------- | ------ | ------ | | FLIGHT | 1 | 0001 | | HEALING | 4 | 0100 | | result | 5 | 0101 |

The computer flips the bits for all the 1s in both numbers. The result is 0101, which represents 5 in binary.

Computers have gotten fast enough and the performance aspect of bit flags has become largely irrelevant, but in certain cases, like physics engines that need to check thousands of conditions in the fastest possible way, it still matters.

Most common bitwise operations

The operations we use to manipulate bits are called "bitwise operations". Here are the most common ones:

OR (`|`)

Compares two numbers and returns a 1 for any 1 found. For example:

| power | binary | number | | ----------- | ------ | ------ | | FLIGHT | 0001 | 1 | | TELEPATHY | 0010 | 2 | | OR result | 0011 | 3 |

You can think of it like the or keyword when working with Boolean numbers, except it applies to every bit in a number.

For example, if we wanted a hero to have both FLIGHT and TELEPATHY, we would write:

var power_flags = FLIGHT | TELEPATHY

This sets the bits for both FLIGHT and TELEPATHY.

AND (`&`)

Compares two numbers on a bit level and returns a number where a bit is 1 if both bits of the original numbers are 1. It's similar to the and keyword with Boolean numbers, except it applies to each bit in the input numbers.

| | binary | number | | ------------ | ------ | ------ | | | 0001 | 1 | | | 0011 | 3 | | AND result | 0001 | 1 |

Another example:

| | binary | number | | ------------ | ------ | ------ | | | 0001 | 1 | | | 0100 | 4 | | AND result | 0000 | 0 |

To check if a hero has the FLIGHT flag, we would write:

func has_flight_power(power_flags: int) -> bool:
    return power_flags & FLIGHT != 0

If power_flags has FLIGHT, the result of power_flags & FLIGHT will be 1. Otherwise, it will be 0.

Yes! It's pretty confusing. I recommend reading this entire thing a few times.

The two other operators are less useful for bit flags, so we'll explain them very quickly.

XOR (`^`)

XOR or "exclusive or" sets a bit to 1 only if exactly one of the bits in the two compared numbers is 1.

| | binary | number | | ------------ | ------ | ------ | | | 0001 | 1 | | | 0011 | 3 | | XOR result | 0010 | 2 |

NOT (`~`)

NOT inverts the bits of a number.

| | binary | number | | ------------ | ------ | ------ | | | 0011 | 3 | | NOT result | 1100 | 12 |

Bit shifting

Another common operation is "bit shifting". This is when you move all the bits in a number to the left or right. This is useful for multiplying or dividing by powers of 2.

Left shift (`<<`)

Moves all the bits in a number to the left by a certain number of steps. This is equivalent to multiplying the number by 2 for each step.

Let's try it:

| | binary | number | | ------ | ------ | ------ | | | 0001 | 1 | | << 1 | 0010 | 2 | | << 2 | 0100 | 4 | | << 3 | 1000 | 8 |

This is particularly useful for writing your own bit flags; instead of mentally multiplying by 2, you can just write:

const FLIGHT    = 1 << 0
const TELEPATHY = 1 << 1
const HEALING   = 1 << 2
# ... and so on

Right shift (`>>`)

Right shift is the opposite of left shift. It moves all the bits in a number to the right by a certain number of steps. This is equivalent to dividing the number by 2 for each step.

| | binary | number | | ------ | ------ | ------ | | | 1000 | 8 | | >> 1 | 0100 | 4 | | >> 2 | 0010 | 2 | | >> 3 | 0001 | 1 |