| description |
|---|
Binary problems are quite rare in interviews and even online assessments but it's always good to know |
- Check for overflow/underflow
- Negative numbers (they use the twos complement system)
The XOR (^) operator is quite commonly used to solve binary problems, these are some important properties you should familiarize yourself with:
n ^ n = 0n ^ m == m ^ nn ^ (m ^ k) == (n ^ m) ^ kn ^ 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) - Multiply by
$$2^K$$ :num << k - Divide by
$$2^K$$ :num >> k - Check if number is power of 2:
(num & num - 1) == 0ornum & (-num) == num - Remove rightmost set bit:
num & (num - 1) - Swapping two variables (only positive numbers):
num1 ^= num2; num2 ^= num1; num1 ^= num2
For more information and tricks, refer to this post.