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
FalseBitMap
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
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
FalseMore 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 bytes1136 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 1011Binary 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 10Shifting 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/210
2Or 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) # 102412
96
1
2
4
8
16
1024AND, 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) # 0101AND
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 1Checking 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
4The 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
TrueTurning 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 bit5 in binary is 101
7 in binary is 111
37 in binary is 100101
53 in binary is 110101Turning 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 bit53 in binary is 110101
49 in binary is 110001
52 in binary is 110100Flipping 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 bit53 in binary is 110101
52 in binary is 110100
55 in binary is 110111Using 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
Falseimport sys
print(f"bit_visited: {sys.getsizeof(bit_visited)} bytes")bit_visited: 28 bytesIt 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
FalseFile 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:
000
001
010
011
100
101
110
111If we label each bit:
ABC
000 # none of them
001 # C
010 # B
011 # BC
100 # A
101 # AC
110 # AB
111 # ABCSo, 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 TrueThat’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 TrueWhen we have visited the col/row, we just mark it as visited.
row_visited |= 1 << row
col_visited |= 1 << colComplete 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())403208-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