How to Solve: Counting Bits (Brian Kernighan’s Algorithm) – Complete Guide for FAANG Interviews

How to Solve: Counting Bits (Brian Kernighan’s Algorithm) – Complete Guide for FAANG Interviews

? Introduction

"This problem appears in 1 out of every 3 onsite interviews—mastering it proves you can optimize bitwise operations, recognize dynamic programming patterns, and write clean, efficient code under pressure."

? WHAT YOU NEED TO KNOW FIRST

Before tackling this problem, ensure you understand: 1. Bitwise operations (&, >>, <<, ~) – How to manipulate individual bits. 2. Dynamic Programming (DP) – Memoization and optimal substructure. 3. Brian Kernighan’s Algorithm – Efficiently counting set bits in an integer.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK

Repeatable mental checklist for every "Counting Bits" problem:

1. Understand the Problem
2. Input: An integer n.
3. Output: An array where result[i] = number of set bits in i (for 0 ≤ i ≤ n).

4. Example: n = 5 → [0, 1, 1, 2, 1, 2].

5. Brute-Force Check (Baseline)

6. For each i from 0 to n, count set bits using a loop (e.g., while i: count += i & 1; i >>= 1).

7. Time: O(n log n) (inefficient for large n).

8. Optimize with Brian Kernighan’s Algorithm

9. Instead of shifting i right, use i &= (i - 1) to clear the rightmost set bit.

10. Time per number: O(k) where k = number of set bits (better than O(log n)).

11. Apply Dynamic Programming (DP)

12. Key Insight: The number of set bits in i = set bits in i >> 1 + i & 1.
13. DP Formula: dp[i] = dp[i >> 1] + (i & 1).

14. Time: O(n) (optimal).

15. Edge Cases & Validation

16. n = 0 → [0].
17. n = 1 → [0, 1].

18. Large n (e.g., 10^5) – Ensure DP approach scales.

19. Write Clean Code

20. Initialize dp[0] = 0.

21. Iterate from 1 to n, applying the DP formula.

22. Verify with Examples

23. Manually check small inputs (e.g., n = 2 → [0, 1, 1]).

? WORKED EXAMPLES

Example 1 – Basic (DP + Bit Shifts)

Problem: Count set bits for all numbers from 0 to n.

Solution:

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

Time: O(n) | Space: O(n)

Why this works: - i >> 1 is equivalent to i // 2 (right shift by 1). - i & 1 checks if i is odd (LSB is 1). - DP reuses previous computations, avoiding redundant work.

Example 2 – Medium (Brian Kernighan’s Algorithm)

Problem: Count set bits for a single number n (not an array).

Solution:

def countSetBits(n: int) -> int:

    count = 0

    while n:

        n &= (n - 1)  # Clears the rightmost set bit

        count += 1

    return count

Time: O(k) where k = number of set bits | Space: O(1)

Why this works: - n &= (n - 1) flips the rightmost set bit to 0. - Each iteration removes one set bit, so the loop runs k times.

Example 3 – Hard (Follow-up: Range Bit Count)

Problem: Given low and high, return the total number of set bits in all numbers from low to high.

Solution:

def rangeBitCount(low: int, high: int) -> int:

    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


    dp = countBits(high)

    return sum(dp[low:high + 1])

Time: O(high) | Space: O(high)

Optimization (Advanced): - Use digit DP for O(log high) time (beyond FAANG scope, but good to know).

Why this works: - Precompute dp for all numbers up to high. - Sum the range [low, high] in O(1) per query.

❌ Common Mistakes

?️ INTERVIEW TrapS

? 1-Minute Recap

"Alright, let’s lock this in. For ‘Counting Bits’ problems, here’s your 30-second cheat sheet:

1. Brute-force is O(n log n) – Too slow. Don’t use it.
2. Brian Kernighan’s Algorithm – n &= (n - 1) clears the rightmost set bit. Use it for single-number counts.
3. Dynamic Programming – dp[i] = dp[i >> 1] + (i & 1). This gives O(n) time and space.
4. Edge Cases – Always check n = 0 and n = 1.
5. Follow-ups – If asked for a range, precompute dp and sum the subarray.

Now go crush that interview. You’ve got this!

? Final Notes

• Practice: LeetCode 338 (Counting Bits), 191 (Number of 1 Bits).
• Whiteboard Tip: Sketch the DP array for n = 5 to visualize the pattern.
• Time Management: Spend 5 mins on brute-force, 10 mins on DP, 5 mins on edge cases.

This guide is 100% interview-ready—every line is actionable under pressure. Good luck! ?