# Binary

Binary problems are quite rare in interviews and even online assessments but it's always good to know

## Corner cases

Check for overflow/underflow

Negative numbers (they use the twos complement system)

## XOR behavior

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`

## Common bitmasks

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`

## Techniques

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) == 0`

or`num & (-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.

Last updated