DSA-Bit-Manipulation-Lab 🚀

Master bit manipulation — XOR tricks, Brian Kernighan, bitmask DP, power checks. 40+ problems with O(1) solutions. FAANG interview essential.

Built by Kushagra Bansal | Founder @ Project Lab India

---

🎯 Learning Objectives

• Master all bitwise operators: &, |, ^, ~, <<, >>
• Solve problems in O(1) that normally take O(n)
• Implement Brian Kernighan, XOR swap, power-of-two checks
• Apply bitmask DP for subset problems

📌 Topics Covered

#	Topic	Trick	Frequency
1	XOR Tricks	a^a=0, a^0=a	⭐⭐⭐⭐⭐
2	Count Set Bits	Brian Kernighan: n&(n-1)	⭐⭐⭐⭐⭐
3	Power of Two	n&(n-1)==0	⭐⭐⭐⭐⭐
4	Bit Masking	mask=(1<<k)	⭐⭐⭐⭐
5	Set/Clear/Toggle	OR/AND-NOT/XOR	⭐⭐⭐⭐
6	Bitmask DP	2^n subsets	⭐⭐⭐⭐

📋 Problem Statements

P1 — Single Number: Every element appears twice except one. Find it. [2,2,1]→1

P2 — Count Set Bits: Count 1-bits in n. 11(1011)→3

P3 — Power of Two: O(1) check. 16→True, 18→False

P4 — Missing Number: Array has [0..n] minus one. Find it. [3,0,1]→2

P5 — Two Single Numbers: Two appear once, rest twice. [1,2,3,2,1,4]→[3,4]

P6 — Add Without +: Use XOR+carry. 5+3=8

P7 — Subsets via Bitmask: All 2^n subsets. [1,2,3]→8 subsets

P8 — Reverse 32 Bits: Mirror binary representation.

---

⏱️ Complexity Summary

See notes/learning_notes.md for full complexity analysis.

---

⚡ Quick Start

git clone https://github.com/kushagrabansal-IOT/DSA-Bit-Manipulation-Lab.git
cd DSA-Bit-Manipulation-Lab
python solutions/main.py
python -m pytest tests/ -v

---

📦 Project Structure

DSA-Bit-Manipulation-Lab/
├── solutions/
│   └── main.py         ← All solutions (run this)
├── tests/
│   └── test_main.py    ← pytest test suite
├── notes/
│   └── learning_notes.md
├── LICENSE
└── README.md

---

🚀 Future Improvements

• Add C++ / Java implementations
• Add LeetCode links for all problems
• Add visual diagrams
• Add more advanced variants

---

👨‍💻 Author

Kushagra Bansal — Founder @ Project Lab India, Jaipur 🔬 DSA • OOPS • DBMS • IoT • Competitive Programming 🏆 Innovation Award Recipient • IEEE Member 🛒 radiomarket.in

---

📄 License

MIT License — See LICENSE

---

⭐ Star if it helped! | 🍴 Fork it | 📢 Share it