30. Bit Manipulation Tricks: Number of 1 Bits (Hamming Weight), Counting Bits & Missing Number • Data Structures & Algorithms: Blind 75 & Big Tech Interview Prep • Rishabh Ki Kaksha

Data Structures & Algorithms: Blind 75 & Big Tech Interview Prep › 30. Bit Manipulation Tricks: Number of 1 Bits (Hamming Weight), Counting Bits & Missing Number

40 mins

← Prev

Course Syllabus

Module 1: Big-O Asymptotics, Arrays & Sliding Window

01. Time & Space Complexity Masterclass: Big-O, Big-Theta, Big-Omega & Amortized Analysis 02. Arrays & Hashing: Two Sum, Contains Duplicate & Valid Anagram (Hash Table Lookups) 03. Prefix Sum & Kadane's Algorithm (Maximum Subarray Problem in O(N)) 04. Sliding Window Pattern: Fixed vs Dynamic Windows (Best Time to Buy/Sell Stock)

Module 2: Two Pointers & Binary Search Systems

05. Two Pointers Pattern: Valid Palindrome, 3Sum & Container With Most Water 06. Binary Search Foundations: Search in Rotated Sorted Array & Find Minimum 07. Binary Search on Answer Space: Koko Eating Bananas & Capacity to Ship Packages

Module 3: Linked Lists & Fast-Slow Pointer Patterns

08. Singly vs Doubly Linked Lists & In-Place Pointer Manipulation (Reverse Linked List) 09. Fast & Slow Pointer (Floyd's Cycle Detection): Linked List Cycle & Middle Node 10. Merging & Reordering: Merge Two Sorted Lists, Reorder List & Remove Nth Node

Module 4: Stacks, Queues & Monotonic Stack Architecture

11. Stack Fundamentals: Valid Parentheses & Min Stack in O(1) Time 12. Monotonic Stack Pattern: Daily Temperatures & Next Greater Element 13. Hard Stack Coding: Largest Rectangle in Histogram & Trapping Rain Water

Module 5: Trees, Binary Search Trees & DFS/BFS Traversals

14. Binary Tree Architecture: Max Depth, Same Tree & Invert Binary Tree 15. BFS Level-Order Traversal & Binary Tree Right Side View 16. Binary Search Tree (BST) Properties: Validate BST & Lowest Common Ancestor (LCA) 17. Tree Path Sums & Serialize / Deserialize Binary Tree (Hard)

Module 6: Heaps, Priority Queues & Top-K Problems

18. Min Heap & Max Heap Internals: Array Representation & Heapify in O(N) 19. Top-K Elements Pattern: Kth Largest Element in an Array & Top K Frequent Elements 20. Two-Heap Pattern: Find Median from Data Stream (Hard)

Module 7: Graphs, Topological Sort & Shortest Paths (Dijkstra)

21. Graph Representations (Adjacency Matrix vs List) & DFS/BFS Traversal 22. Matrix Graph Traversal: Number of Islands, Max Area of Island & Clone Graph 23. Topological Sort (Kahn's Algorithm): Course Schedule I & II (Cycle Detection) 24. Disjoint Set Union (DSU / Union-Find): Redundant Connection & Number of Connected Components

Module 8: Dynamic Programming, Backtracking & Bit Manipulation

25. Backtracking Pattern: Subsets, Permutations, Combination Sum & Word Search 26. 1D Dynamic Programming: Climbing Stairs, House Robber & Coin Change 27. Longest Increasing Subsequence (LIS): O(N^2) DP vs O(N log N) Patience Sort 28. 2D Dynamic Programming: Unique Paths, Longest Common Subsequence (LCS) & Edit Distance 29. 0/1 Knapsack Pattern & Partition Equal Subset Sum 30. Bit Manipulation Tricks: Number of 1 Bits (Hamming Weight), Counting Bits & Missing Number

Interactive Lesson Studio

# 30. Bit Manipulation Tricks: Number of 1 Bits (Hamming Weight), Counting Bits & Missing Number

> DSA Blind 75 Notes by Rishabh - Topic 30

---

### 1. Essential Bitwise Operators Cheat Sheet ⚡

*   `x & (x - 1)`: **Clears the lowest set bit (1-bit) in $O(1)$!**
*   `x ^ x = 0`: **XOR with self cancels out to 0!**
*   `x ^ 0 = x`: **XOR with 0 keeps value intact!**
*   `1 << k`: **Sets $k$-th bit ($2^k$).**

---

### 2. LeetCode #191: Number of 1 Bits (Brian Kernighan's Algorithm)

```python
def hammingWeight(n: int) -> int:
    count = 0
    while n:
        n = n & (n - 1) # ⚡ Removes lowest 1-bit instantly!
        count += 1
    return count
```
*Time Complexity:* $O(\text{Number of set bits})$ (Runs strictly in number of 1s, not 32 bits!).

---

### 3. LeetCode #268: Missing Number ($O(N)$ Time, $O(1)$ Space via XOR)

```python
def missingNumber(nums: list[int]) -> int:
    res = len(nums)
    for i, num in enumerate(nums):
        res ^= i ^ num # Duplicates cancel out, missing number remains!
    return res
```

---

### 4. LeetCode #338: Counting Bits ($O(N)$ DP + Bit Trick)

$$dp[i] = dp[i >> 1] + (i \& 1)$$

```python
def countBits(n: int) -> list[int]:
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = dp[i >> 1] + (i & 1)
    return dp
```

---

### 5. Master Comparison Matrix

| Problem | Bit Trick | Time Complexity | Space Complexity |
| :--- | :--- | :--- | :--- |
| **Hamming Weight** | `n & (n - 1)` | $O(\text{Set Bits}) \le 32$ | $O(1)$ |
| **Missing Number** | `res ^= i ^ num` | $O(N)$ | $O(1)$ |
| **Single Number (LC #136)**| XOR all numbers | $O(N)$ | $O(1)$ |
| **Counting Bits** | $dp[i] = dp[i // 2] + (i \% 2)$ | $O(N)$ | $O(N)$ |
| **Reverse Bits (LC #190)**| `(res << 1) | (n & 1)` | $O(1)$ (32 Iterations) | $O(1)$ |

---

### 6. Interview Ke 3 Sawal Is Topic Se

1. **Sum of Two Integers without using `+` or `-` (LeetCode #371) kaise implement hota hai?** -> Bitwise addition: `carry = (a & b) << 1`, `sum = a ^ b`; loop until carry becomes 0.
2. **Reverse Bits me integer 32-bit mask kaise lagate hain?** -> Python arbitrary precision integers ke liye `n & 0xFFFFFFFF` mask use kiya jata hai.
3. **Single Number II (Number appearing once where all others appear 3 times) kaise solve hota hai?** -> Har bit position $0$ to $31$ par total 1s count karke modulo 3 (`count % 3`) lete hain.

---
**Course Completed:** Data Structures & Algorithms (Blind 75 All 30 Lessons Completed!) 🎉🚀🏆💎🔥

Loading lesson content...

JavaScript

Full IDE

Live Execution Terminal

Click "Execute Live" to run code.
                

Lesson Mastery AI Quiz

AI Doubt Solver

CERTIFICATE OF COMPLETION

Rishabh Gehlot

PHP 8+ & Laravel 11 Master Track