BitMap

Let’s recall why we do need set.

Assuming we have 30 cities (identified by number/id from 0 to 29). We want to keep track of the cities we have visited

visited = [1, 5, 6, 8, 10]

def is_visited(visited, city):
    # O(n)
    for visited_city in visited:
        if visited_city == city:
            return True
    return False

print(is_visited(visited, 6))
print(is_visited(visited, 7))

True
False

Ok, but that’s O(n)

We then optimized it using boolean array

bool_visited = [False] * 30 # 30 cities

bool_visited[1] = True
bool_visited[5] = True
bool_visited[6] = True
bool_visited[8] = True
bool_visited[10] = True

def is_visited(visited, city):
    # O(1)
    return visited[city]

print(is_visited(bool_visited, 6))
print(is_visited(bool_visited, 7))

True
False

More memory efficient way

Our code is O(1) but our storage complexity is O(n)

It’s not a big deal, but we can do better.

Let’s check how much memory we need to store a boolean array of size 30:

import sys

# Integer
int_value = 1
print(f"Integer: {sys.getsizeof(int_value)} bytes")

# Boolean
bool_value = True
print(f"Boolean: {sys.getsizeof(bool_value)} bytes")

# Array of boolean
bool_array = [True] * 30
print(f"Array of booleans: {sys.getsizeof(bool_array) + sum(map(sys.getsizeof, bool_array))} bytes")

Integer: 28 bytes
Boolean: 28 bytes
Array of booleans: 1136 bytes

1136 bytes

Can we do better?

Yes, it’s possible to only use 28 bytes!

Bit Representation

Let’s step back for a while…

Every integer is represented as a sequence of bits (binary digits), and every bit is either 0 or 1.

For example, the decimal number five has a binary representation of 101:

# print a number and its binary representation

def print_binary(number):
    print(f"{number} in binary is {bin(number)[2:]}")

print_binary(1)
print_binary(5)
print_binary(10)
print_binary(11)

1 in binary is 1
5 in binary is 101
10 in binary is 1010
11 in binary is 1011

Binary Operations

The basic binary operations are shifting left, shifting right, bitwise AND, bitwise OR, bitwise NOT, and bitwise XOR.

Shifting

# shifting left
print("Shifting left")
print_binary(1)
print_binary(1 << 1)
print_binary(1 << 2)

# shifting right
print()
print("Shifting right")
print_binary(11)
print_binary(11 >> 1)
print_binary(11 >> 2)

Shifting left
1 in binary is 1
2 in binary is 10
4 in binary is 100

Shifting right
11 in binary is 1011
5 in binary is 101
2 in binary is 10

Shifting also has the effect of multiplying or dividing the number by a power of two.

def multiply_by_two(number):
    return number << 1 # number * 2 ^ 1

def divide_by_two(number):
    return number >> 1

print(multiply_by_two(5)) # 5 * 2
print(divide_by_two(5)) # 5/2

10
2

Or more generally, shifting left by n bits is equivalent to multiplying by 2^n

print(3 << 2) # 3 * 2^2
print(3 << 5) # 3 * 2^5 

print(1 << 0) # 1
print(1 << 1) # 2
print(1 << 2) # 4
print(1 << 3) # 8
print(1 << 4) # 16
print(1 << 10) # 1024

AND, OR, XOR, NOT

print("AND")
print_binary(5)
print_binary(7)

print_binary(5 & 7) # 0100
print()

print("OR")
print_binary(5)
print_binary(4)

print_binary(5 | 4) # 0101
print()

print("XOR")
print_binary(5)
print_binary(4)

print_binary(5 ^ 4) # 0101

AND
5 in binary is 101
7 in binary is 111
5 in binary is 101

OR
5 in binary is 101
4 in binary is 100
5 in binary is 101

XOR
5 in binary is 101
4 in binary is 100
1 in binary is 1

Checking if a bit is set

To check if the i-th (0 based) bit is set, we can just AND the number with 1 << i

print_binary(5)

print(5 & 1 << 0)
print(5 & 1 << 1)
print(5 & 1 << 2)

5 in binary is 101
1
0
4

The result will be 0 if the bit is not set, and non-zero otherwise.

print_binary(5)

print(5 & 1 << 0 != 0)
print(5 & 1 << 1 != 0)
print(5 & 1 << 2 != 0)

5 in binary is 101
True
False
True

Turning on a bit

To turn on the i-th bit, we can OR the number with 1 << i

print_binary(5)
print()

print_binary(5 | 1 << 1) # turning on 1st bit
print_binary(5 | 1 << 5) # turning on 5th bit

print()
print_binary(37 | 1 << 4) # turning on 4th bit

5 in binary is 101

7 in binary is 111
37 in binary is 100101

53 in binary is 110101

Turning off a bit

To turn off the i-th bit, we can AND the number with ~(1 << i)

~ is the bitwise NOT operator

Hint:

dec	bin
`1 << 4`	`0010000`
`~(1 << 4)`	`1101111`

print_binary(53)

print()
print_binary(53 & ~(1 << 2)) # turning off 2nd bit
print_binary(53 & ~(1 << 0)) # turning off 0th bit

53 in binary is 110101

49 in binary is 110001
52 in binary is 110100

Flipping a bit

To flip the i-th bit, we can XOR the number with 1 << i

print_binary(53)

print()
print_binary(53 ^ 1 << 0) # flipping 0th bit
print_binary(53 ^ 1 << 1) # flipping 1st bit

53 in binary is 110101

52 in binary is 110100
55 in binary is 110111

Using Bitmap

Let’s see how we can use bitmaps to store the visited cities

bit_visited = 0

bit_visited |= 1 << 1
bit_visited |= 1 << 5
bit_visited |= 1 << 6
bit_visited |= 1 << 8

def is_visited(visited, city):
    # O(1)
    mask = 1 << city
    return visited & mask != 0

print(is_visited(bit_visited, 6))
print(is_visited(bit_visited, 7))

True
False

import sys

print(f"bit_visited: {sys.getsizeof(bit_visited)} bytes")

bit_visited: 28 bytes

It only uses 28 bytes! While the boolean array uses 1136 bytes.

Use Cases

Feature Toggle

Let’s say we have a feature toggle of 100 features, and we want to enable/disable them.

class FeatureFlags:
    def __init__(self):
        self.flags = 0

    def enable_feature(self, feature_id):
        self.flags |= (1 << feature_id)

    def disable_feature(self, feature_id):
        self.flags &= ~(1 << feature_id)
    
    def is_feature_enabled(self, feature_id):
        mask = 1 << feature_id
        return self.flags & mask != 0

    def __str__(self):
        return bin(self.flags)

ff = FeatureFlags()
print("Enable feature 1")
ff.enable_feature(1)
print(f"feature_flags: {ff}")
print(ff.is_feature_enabled(1))

print()

print("Disable feature 1")
ff.disable_feature(1)
print(f"feature_flags: {ff}")
print(ff.is_feature_enabled(1))

print()

print("Enable feature 10 and 20")
ff.enable_feature(10)
ff.enable_feature(20)
print(f"feature_flags: {ff}")
print(ff.is_feature_enabled(10))
print(ff.is_feature_enabled(20))
print(ff.is_feature_enabled(30))

Enable feature 1
feature_flags: 0b10
True

Disable feature 1
feature_flags: 0b0
False

Enable feature 10 and 20
feature_flags: 0b100000000010000000000
True
True
False

File Permission

Are you familiar with chmod?

chmod 755 file.txt

What’s the meaning of that 755? It’s a bitmap representation of file permission!

Let’s try here

All Subsets

The unique sequence of bits can be used to represent a subset of a set.

Let’s do a simple counting:

If we label each bit:

ABC
000 # none of them
001 # C
010 # B
011 # BC
100 # A
101 # AC
110 # AB
111 # ABC

So, given a set, to return all subsets, we can just iterate from 0 to 2^n - 1 and check which bit is set.

def subsets(groups):
    for i in range(1 << len(groups)):
        subset = []
        for j in range(len(groups)):
            if i & (1 << j):
                subset.append(groups[j])
        yield subset

for subset in subsets(["A", "B", "C"]):
    print(subset)

[]
['A']
['B']
['A', 'B']
['C']
['A', 'C']
['B', 'C']
['A', 'B', 'C']

8-Rooks

In a chess board, we want to place 8 rooks such that no rook can attack another rook.

How to check if a rook is occupying a column? The following is the slow way:

from typing import List

boards: List[List[bool]] = []

def is_valid(board: List[List[bool]], row: int, col: int) -> bool:
    # check whether there is a rook in the same row
    for c in range(col):
        if board[row][c]:
            return False
    # check whether there is a rook in the same column
    for r in range(row):
        if board[r][col]:
            return False
    return True

That’s O(n)

Using bitmap, we can do it in O(1)

row_visited: int = 0
col_visited: int = 0

def is_valid(row_visited: int, col_visited: int, row: int, col: int) -> bool:
    # check whether there is a rook in the same row
    if row_visited & (1 << row) != 0:
        return False
    # check whether there is a rook in the same column
    if col_visited & (1 << col) != 0:
        return False
    return True

When we have visited the col/row, we just mark it as visited.

row_visited |= 1 << row
col_visited |= 1 << col

Complete solution:

def solve_eight_rooks(n=8):
    def solve(row, columns):
        if row == n:
            return 1
        count = 0
        for col in range(n):
            if not (columns & (1 << col)):
                count += solve(row + 1, columns | (1 << col))
        return count

    return solve(0, 0)

print(solve_eight_rooks())

8-Queens

8-Queens is similar to 8-Rooks, but we need to check the diagonal as well:

diag1_visited: int = 0
diag2_visited: int = 0