Bit Manipulation

Bit Manipulation in DSA (Java)

Master bitwise operations for optimized problem solving and interview success.

📌 Topics Covered

1. Basic Operations
2. Advanced Questions
3. FAQs

💡 Bit manipulation allows solving problems in O(1) or O(log n) time.

⚡ Basic Bit Operations

1. Set a Bit

num |= (1 << i)

2. Clear a Bit

num &= ~(1 << i)

3. Toggle a Bit

num ^= (1 << i)

4. Check if Bit is Set

(num & (1 << i)) != 0

🚀 Advanced Questions

5. Count Set Bits (Brian Kernighan)

int countSetBits(int num) { int count = 0; while (num > 0) { num &= (num - 1); count++; } return count; }

6. Find MSB

Use log or bit shifting approach

7. Find LSB

num & (-num)

8. AND, OR, XOR

• & → AND
• | → OR
• ^ → XOR

🎯 Conclusion

Bit manipulation is one of the most powerful tools in DSA for optimizing performance and solving complex problems efficiently.

❓ FAQs

1. Works in all languages like C++, Python, Java
2. Useful beyond low-level programming
3. May reduce readability but improves performance
4. Used in cryptography
5. Practice via DSA problems and tutorials