Bit Manipulation

Two's complement

Binary represenation of negative numbers.

Example (4 bits):

-8

Decimal	-8	-7	-6	-5	-4	-3	-2	-1
Binary	1000	1001	1010	1011	1100	1101	1110	1111

Decimal	0	1	2	3	4	5	6	7
Binary	0000	0001	0010	0011	0100	0101	0110	0111

What does the following code do?

print(n >> 1)

Answer: Divides `n` by 2

What does the following code do?

print(n << 1)

Answer: Multiplies `n` by 2

What does the following code do?

print(n & (n-1))

Answer: Turns off the least significant on bit of `n`

What does the following code do?

print(n & (n-1) == 0)

Answer: Checks if `n` is a power of 2

What does the following code do?

print(n & (-n))

Answer: Isolates the least significant on bit.

What does the following code do?

def magic(n):
    i = 0
    while n:
        i += 1
        n &= n-1

Answer: Counts on bits in `n`.

Bit masks

0 = 0000    4 = 0100    8 = 1000    C = 1100
1 = 0001    5 = 0101    9 = 1001    D = 1101
2 = 0010    6 = 0110    A = 1010    E = 1110
3 = 0011    7 = 0111    B = 1011    F = 1111

Leetcode Problems

Solve at your own pace, choosing problems of varying difficulty levels.
Set the number of problems based on your available study time.

https://leetcode.com/problem-list/bit-manipulation/