Bit Manipulation

Starred by 25+ users, GitHub Repo: LeetCode Pattern 500 offers:

  • 500 solutions for LeetCode problems in Python and Java
  • 17 notes on essential concepts related to data structures and algorithms
  • 130 patterns for solving LeetCode problems

bit manipulation

intro

# bitmasking
# start from: mask = 0
# checking: mask & 1<<k == 0, if equals 0 means not mask 1<<k yet
# masking: mask = mask | 1<<k
# notice: we can also use "mask = mask ^ 1<<k" to mask for different purpose (toggle)
mask = 0
bin(mask) # 0b0
mask & 1<<3 # 0
mask |= 1<<3 # 8
bin(mask) # 0b1000
mask & 1<<3 # 8
mask & 1<<5 # 0

# xor
5 ^ 5 # 0
5 ^ 5 ^ 3 # 3

# shift
>>
<<

# not
~

# turn int number to 4-byte string (length = 4)
# 256 == 8 bits == 1 byte
bin(0xff) # '0b11111111'
def int_to_string(val):
    byte_array = [(val >> (i * 8)) & 0xFF for i in range(4)][::- 1]
    char_array = [chr(byte) for byte in byte_array]
    string = ''.join(char_array)
    return string

# turn 4-byte string to int number
def string_to_int(string):
    val = 0
    for i, c in enumerate(string):
        val += ord(c) << (8 * (4 - 1 - i)) # use |= here is applicable too
    return val

num = 12345
s = int_to_string(num)
res = string_to_int(s) # 12345

pattern

  • xor
    • xor any num with itself, the result is 0
      • 5 ^ 5 == 0
      • 5 ^ 5 ^ 3 == 3
    • use xor in bitmasking can toggle state
  • shift
    • << to shift left
    • >> to shift right
  • bitmasking
    • can handling sets of states/flags in single int
      • in most cases, size of this set should < 32
    • & to check state
    • | to record state
    • ^ to toggle state