4. Bit Manipulation #

Created Monday 22 June 2020

• We’ve worked with int and float. But never considered using the property of binary digits.
• Bit manipulation is a very elegant and optimized way of solving problems.
• Bit operation are O(1)
• Bit manip has many applications in competitive programming.

Where is Bit manip used:

1. Competitive Programming
2. Data Compression

Note: Everything happens in standard notation(2’s complement form) Operator precedence:

1. Complement (~)
2. Shift operators (<<) and (>>)
3. Bitwise manip(^, &, |)

Difference between logical and bitwise ops:

1. Bitwise ops don’t short circuit, logical do.
2. XOR operator is absent for logical ops.

Approach:

1. Choose the operator.
2. Find the mask. Consider 2^i when i is given. Else use +1, -1, *-1
3. Make the mask using the least ops.
4. Apply the mask.