Number of 1 Bits (Hamming Weight)

📋

Problem

Imagine you are working on a network packet analyzer that needs to quickly count how many flags are set in a packet header represented as a 32-bit integer.

Write a function that takes an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight). Input is a 32-bit unsigned integer. Output is an integer count of set bits.

The input is a 32-bit unsigned integer.You must handle the input efficiently.

Edge cases: n = 0 → output 0 (no bits set)n = 4294967295 (all bits set) → output 32n = 1 (only least significant bit set) → output 1

</>

IDE

def hammingWeight(n: int) -> int:public int hammingWeight(int n)int hammingWeight(unsigned int n)function hammingWeight(n)

def hammingWeight(n: int) -> int:
    # Write your solution here
    pass

class Solution {
    public int hammingWeight(int n) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int hammingWeight(unsigned int n) {
    // Write your solution here
    return 0;
}

function hammingWeight(n) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Not counting any bits or returning zero prematurely.✅ Ensure loop iterates 32 times and sums n & 1 each iteration.

Wrong: 31Off-by-one error when input has all bits set (32 bits).✅ Iterate full 32 bits and do not stop early; count all bits correctly.

Wrong: Wrong count for highest bit set input (e.g., 0 instead of 1)Ignoring or missing the most significant bit during counting.✅ Ensure loop covers all 32 bits including the highest bit.

Wrong: Incorrect count for alternating bits pattern (e.g., 15 instead of 16)Miscounting bits due to incorrect bitwise operations or skipping bits.✅ Use Kernighan’s algorithm or carefully check each bit in a loop.

Wrong: Timeout or no outputInefficient brute force approach causing TLE on large inputs.✅ Implement Brian Kernighan’s algorithm to reduce iterations to number of set bits.

✓

Test Cases

Try testing inputs with zero and all bits set to catch base case bugs.

Consider tricky inputs that expose off-by-one or greedy counting errors.

Think about the time complexity and how to optimize counting set bits efficiently.

t1_01basic

Input{"n":11}

Expected3

⏱ Performance - must finish in 2000ms

The binary representation of 11 is 00000000000000000000000000001011 which has three '1' bits at positions 0, 1, and 3.

💡 Count the number of bits set to 1 in the binary representation.

💡 Use bitwise AND with 1 and right shift the number to check each bit.

💡 Iterate 32 times since input is 32-bit unsigned integer and sum the bits.

Why it failed: Incorrect count of set bits. Likely missed checking all 32 bits or incorrect bitwise operations. Fix by iterating exactly 32 times and summing n & 1 each iteration.

✓ Correctly counted all set bits in the canonical example.

t1_02basic

Input{"n":29}

Expected4

⏱ Performance - must finish in 2000ms

29 in binary is 00000000000000000000000000011101 which has four '1' bits at positions 0, 2, 3, and 4.

💡 Convert the number to binary and count the ones.

💡 Use bitwise operations to count set bits efficiently.

💡 Check each bit by n & 1 and right shift n until all bits are processed.

Why it failed: Returned wrong count of set bits. Possibly stopped early or miscounted bits. Fix by ensuring loop runs 32 times and accumulates bits correctly.

✓ Correctly counted all set bits for a different input.

t2_01edge

Input{"n":0}

Expected0

⏱ Performance - must finish in 2000ms

Zero has no bits set, so the count is 0.

💡 Check what happens when input is zero.

💡 No bits should be set in zero, so count should be zero.

💡 Ensure your loop or method handles zero correctly without errors.

Why it failed: Returned non-zero count for input zero. Possibly not handling zero input correctly or summing bits incorrectly. Fix by ensuring zero input returns zero count.

✓ Correctly handled zero input with zero set bits.

t2_02edge

Input{"n":4294967295}

Expected32

⏱ Performance - must finish in 2000ms

4294967295 is 32 bits all set to 1, so the count is 32.

💡 Test the maximum 32-bit unsigned integer with all bits set.

💡 Count should be 32 since all bits are 1.

💡 Make sure your method counts all bits and does not stop early.

Why it failed: Returned less than 32 for all bits set input. Likely loop stops early or bit masking is incorrect. Fix by iterating full 32 bits and summing correctly.

✓ Correctly counted all 32 bits set.

t2_03edge

Input{"n":2147483648}

Expected1

⏱ Performance - must finish in 2000ms

2147483648 is 10000000000000000000000000000000 in binary with only the most significant bit set.

💡 Check input with only the highest bit set.

💡 Count should be exactly 1 for this input.

💡 Ensure your method handles bits in all positions, including the highest.

Why it failed: Returned zero or incorrect count for highest bit set input. Possibly ignoring highest bit or incorrect bit shifts. Fix by iterating all 32 bits and checking each bit.

✓ Correctly counted the single highest bit set.

t3_01corner

Input{"n":15}

Expected4

⏱ Performance - must finish in 2000ms

15 in binary is 00000000000000000000000000001111 with four bits set.

💡 Beware of greedy approaches that count only some bits.

💡 Use Brian Kernighan’s algorithm to count set bits by clearing the lowest set bit repeatedly.

💡 Implement loop: while n != 0, n = n & (n-1), increment count each iteration.

Why it failed: Incorrect count due to greedy approach or partial counting. Fix by using n = n & (n-1) loop to count all set bits correctly.

✓ Correctly counted bits using Kernighan’s algorithm or equivalent.

t3_02corner

Input{"n":2147483647}

Expected31

⏱ Performance - must finish in 2000ms

2147483647 is 01111111111111111111111111111111 in binary with 31 bits set.

💡 Check for off-by-one errors in bit counting.

💡 Ensure you count all bits except the highest bit which is zero here.

💡 Verify loop runs exactly 32 times or until n becomes zero.

Why it failed: Returned 32 or incorrect count due to off-by-one error. Fix by correctly iterating and counting bits without overshooting.

✓ Correctly counted 31 bits set without off-by-one errors.

t3_03corner

Input{"n":2863311530}

Expected16

⏱ Performance - must finish in 2000ms

2863311530 in binary is 10101010101010101010101010101010 with exactly 16 bits set.

💡 Beware of confusing 0/1 bits or miscounting alternating bits.

💡 Use bitwise operations carefully to count set bits in alternating pattern.

💡 Check each bit or use Kernighan’s algorithm to count all set bits.

Why it failed: Incorrect count due to miscounting alternating bits pattern. Fix by correctly iterating all bits or using n = n & (n-1) method.

✓ Correctly counted 16 set bits in alternating pattern.

t4_01performance

Input{"n":4294967295}

Expectednull

⏱ Performance - must finish in 2000ms

Input is the maximum 32-bit unsigned integer with all bits set (n=4294967295). The solution must run in O(1) or O(k) time where k is number of set bits, completing within 2 seconds.

💡 Brute force checking each bit is O(1) but can be optimized.

💡 Use Brian Kernighan’s algorithm to reduce iterations to number of set bits.

💡 Avoid naive loops that do unnecessary work; use bit manipulation tricks.

Why it failed: Solution timed out due to O(32) brute force or worse complexity. Fix by implementing Brian Kernighan’s algorithm or built-in bit count functions for O(k) time.

✓ Solution runs efficiently within time limits using optimal bit counting.

Practice

1. Consider the following Python function to find two missing numbers from 1 to n using XOR partitioning. Given n = 4 and arr = [1, 3], what is the final returned list?

easy

A. [4, 2]

B. [1, 3]

C. [2, 4]

D. [3, 1]

Solution

1. Step 1: Compute xor_all

   xor_all = 1^2^3^4 ^ 1^3 = (1^1)^(2)^(3^3)^(4) = 2 ^ 4 = 6 (binary 110)

2. Step 2: Find rightmost set bit and partition

   set_bit = 6 & (-6) = 2 (binary 010). Partition numbers by this bit: Group 1 (bit set): numbers with bit 2 set -> 2, 3 Group 2 (bit not set): 1, 4 XOR group 1: 2 ^ 3 ^ (arr nums with bit set: 3) = 2 ^ 3 ^ 3 = 2 XOR group 2: 1 ^ 4 ^ (arr nums with bit not set: 1) = 1 ^ 4 ^ 1 = 4 So missing numbers are [2, 4].

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches expected missing numbers [OK]

Hint: Trace XOR and partition by rightmost set bit carefully [OK]

Common Mistakes:

• Misinterpret bit masking for partition
• Mixing order of XOR operations
• Confusing missing numbers with present ones

2. The following code attempts to count set bits for all numbers from 0 to n using Brian Kernighan's trick. Identify the line containing the subtle bug that causes incorrect results.

def countBits(n):
    res = []
    for i in range(1, n + 1):
        count = 0
        x = i
        while x:
            x &= x - 1
            count += 1
        res.append(count)
    return res

medium

A. Line 3: for i in range(1, n + 1):

B. Line 2: res = []

C. Line 5: while x:

D. Line 7: res.append(count)

Solution

1. Step 1: Check loop range correctness

   The loop starts from 1, missing 0, so the count for 0 is never computed or appended.

2. Step 2: Consequence of missing 0

   Result array length is n instead of n+1, causing mismatch and incorrect output for input including 0.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Including 0 is required to match problem specification [OK]

Hint: Loop must start at 0 to include zero count [OK]

Common Mistakes:

• Starting loop at 1 instead of 0
• Appending before counting
• Incorrect while condition

3. Identify the bug in the following code that attempts to check if a number is a power of two:

def isPowerOfTwo(n: int) -> bool:
    while n % 2 == 0:
        n //= 2
    return n == 1

What is the issue?

medium

A. The return statement should check n == 0 instead of n == 1

B. The loop condition should be n > 1 instead of n % 2 == 0

C. Using integer division //= 2 causes infinite loops for odd numbers

D. The code does not handle zero or negative inputs, leading to incorrect results

Solution

1. Step 1: Analyze input handling

   The code does not check if n is positive before the loop, so zero or negative inputs cause incorrect behavior.

2. Step 2: Consequence of missing check

   For n=0 or negative, the loop condition n % 2 == 0 may cause infinite loop or wrong return value.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Proper input validation is required to avoid incorrect results [OK]

Hint: Always check n > 0 before division loops [OK]

Common Mistakes:

• Forgetting zero/negative input checks
• Confusing loop condition with termination condition

4. What is the time complexity of the optimal XOR and partition approach to find two unique numbers in an array of size n?

medium

A. O(n log n) due to sorting step

B. O(n) because it traverses the array a constant number of times

C. O(n^2) because of nested loops in partitioning

D. O(n) but uses O(n) extra space for partitions

Solution

1. Step 1: Identify loops in the algorithm

   The algorithm traverses the array twice: once to XOR all elements, once to partition and XOR groups.

2. Step 2: Analyze time and space complexity

   Each traversal is O(n), no nested loops. Space used is constant (variables only), no extra arrays.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two linear passes, constant space [OK]

Hint: Two passes over array -> O(n) time, O(1) space [OK]

Common Mistakes:

• Confusing with sorting complexity
• Assuming nested loops in partition
• Forgetting constant space usage

5. Consider the following buggy implementation of sum of two integers without + operator. Which line contains the subtle bug that causes incorrect results or infinite recursion?

medium

A. Line 3: base case condition if b == 0

B. Line 6: sum_ calculation using XOR and MASK

C. Line 8: recursive call with sum_ and carry

D. Line 7: carry calculation missing left shift

Solution

1. Step 1: Analyze carry calculation

   Carry must be (a & b) << 1 to shift carry bits to correct position.

2. Step 2: Identify missing left shift causes infinite recursion

   Without shifting, carry never reduces to zero, causing infinite recursion or wrong sum.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Carry missing shift breaks carry propagation [OK]

Hint: Carry must be shifted left by 1 bit [OK]

Common Mistakes:

• Forgetting carry shift
• Incorrect base case
• Not masking intermediate results