Binary
Binary problems are quite rare in interviews and even online assessments but it's always good to know
Last updated
Binary problems are quite rare in interviews and even online assessments but it's always good to know
Last updated
Check for overflow/underflow
Negative numbers (they use the )
The XOR (^) operator is quite commonly used to solve binary problems, these are some important properties you should familiarize yourself with:
n ^ n = 0
n ^ m == m ^ n
n ^ (m ^ k) == (n ^ m) ^ k
n ^ 0 = n
Bitmasks are commonly used to "force" a certain set of bits to be used. They are also used to constraint Python's numbers as Python doesn't use 32 bits for integers so using a manual bitmask is necessary for constraining it
Retrieving the upper 16 bits: 0xffff0000
Retrieving the lower 16 bits: 0x0000ffff
Retrieving all bits in groups of 4: 0xff00ff00
Retrieving all bits in groups of 2: 0xcccccccc
Retrieving all single bits: 0xaaaaaaaa
Test is bit K is set: num & (1 << k) != 0
Set bit K: num |= (1 << k)
Turn off bit K: num &= ~(1 << k)
Toggle bit K: num ^= (1 << k)
Check if number is power of 2: (num & num - 1) == 0
or num & (-num) == num
Remove rightmost set bit: num & (num - 1)
Swapping two variables (only positive numbers): num1 ^= num2; num2 ^= num1; num1 ^= num2
Multiply by : num << k
Divide by : num >> k
For more information and tricks, refer to this