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:
- Competitive Programming
- Data Compression
Note: Everything happens in standard notation(2’s complement form) Operator precedence:
- Complement (~)
- Shift operators (<<) and (>>)
- Bitwise manip(^, &, |)
Difference between logical and bitwise ops:
- Bitwise ops don’t short circuit, logical do.
- XOR operator is absent for logical ops.
Approach:
- Choose the operator.
- Find the mask. Consider 2^i when i is given. Else use +1, -1, *-1
- Make the mask using the least ops.
- Apply the mask.