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 representationdef 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.

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

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 bitprint_binary(5|1<<5) # turning on 5th bitprint()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 bitprint_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 bitprint_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

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 Listboards: List[List[bool]] = []def is_valid(board: List[List[bool]], row: int, col: int) ->bool:# check whether there is a rook in the same rowfor c inrange(col):if board[row][c]:returnFalse# check whether there is a rook in the same columnfor r inrange(row):if board[r][col]:returnFalsereturnTrue

That’s O(n)

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

row_visited: int=0col_visited: int=0def is_valid(row_visited: int, col_visited: int, row: int, col: int) ->bool:# check whether there is a rook in the same rowif row_visited & (1<< row) !=0:returnFalse# check whether there is a rook in the same columnif col_visited & (1<< col) !=0:returnFalsereturnTrue

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