Number of 1 Bits (Hamming Weight)

▶

Steps

setup

Initialize Input Number

The input number n=11 is loaded and converted to its 32-bit binary representation.

💡 Seeing the full 32-bit binary form helps understand which bits are set and which are zero.

Line:

def hammingWeight(n: int) -> int:

💡 The binary form of the input is the foundation for counting set bits.

setup

Convert Number to Binary String

The number 11 is converted to a binary string '1011' for counting '1's.

💡 This conversion is necessary because the count method works on strings, not integers directly.

Line:

return bin(n).count('1')

💡 The binary string representation is the format used to count set bits.

compare

Count '1' at Bit Position 31 (LSB)

Check the least significant bit (bit 31). It is '1', so increment count to 1.

💡 Counting starts from the rightmost bit because it represents the smallest value (2^0).

Line:

return bin(n).count('1')

💡 Each '1' bit contributes to the total count of set bits.

compare

Count '1' at Bit Position 30

Check bit 30. It is '1', so increment count to 2.

💡 Moving leftwards, each bit is checked in order to count all set bits.

Line:

return bin(n).count('1')

💡 Counting each set bit accumulates the total number of ones.

compare

Count '0' at Bit Position 29

Check bit 29. It is '0', so count remains 2.

💡 Bits that are zero do not affect the count.

Line:

return bin(n).count('1')

💡 Only set bits increment the count.

compare

Count '1' at Bit Position 28

Check bit 28. It is '1', so increment count to 3.

💡 Each set bit found adds to the total count.

Line:

return bin(n).count('1')

💡 The total count reflects all set bits found so far.

compare

Check Remaining Bits (27 to 0)

Check bits 27 down to 0, all are zero, so count remains 3.

💡 Bits with zero do not affect the count and can be quickly skipped.

Line:

return bin(n).count('1')

💡 Only bits set to 1 contribute to the count.

reconstruct

Calculate Final Count

The total count of set bits is 3, which is returned as the final answer.

💡 Returning the count completes the algorithm.

Line:

return bin(n).count('1')

💡 The final count represents how many bits are set to 1 in the input.

reconstruct

Output the Result

The algorithm outputs the integer 3, the number of set bits in 11.

💡 This is the final output that answers the problem.

Line:

print(hammingWeight(11))  # Output: 3

💡 The output confirms the count of set bits matches the expected result.

reconstruct

End of Algorithm

The algorithm terminates after returning the count of set bits.

💡 Understanding the end state confirms the algorithm's correctness.

💡 The process is complete and the result is ready for use.

def hammingWeight(n: int) -> int:
    # STEP 1-2: Convert number to binary string and count '1's
    return bin(n).count('1')

if __name__ == '__main__':
    # STEP 9: Output the result
    print(hammingWeight(11))  # Output: 3

📊

Number of 1 Bits (Hamming Weight) - Watch the Algorithm Execute, Step by Step

Watching the algorithm step through the bits visually helps you understand how bit counting works without needing to guess or imagine the process.

Initialize input

A

0

1

0

1

1

=11

B

Convert to binary string

A

0

1

0

1

1

=11

B

Check bit 31

A

0

1

0

1

1

=11

B

────

=

0

1

=1

💡 Bit 31 is set, count increments to 1

Check bit 30

A

0

1

0

1

1

=11

B

──────

=

0

1

1

=2

💡 Bit 30 is set, count increments to 2

Check bit 29

A

0

1

0

1

1

=11

B

──────

=

0

1

1

=2

💡 Bit 29 is zero, count remains 2

Check bit 28

A

0

1

0

1

1

=11

B

────────

=

0

1

1

1

=3

💡 Bit 28 is set, count increments to 3

Check bits 27 to 0

A

0

1

0

1

1

=11

B

────────

=

0

1

1

1

=3

💡 Bits 27 to 0 are zero, count remains 3

Return count

A

0

1

0

1

1

=11

B

────────

=

0

1

1

1

=3

💡 Total set bits counted: 3

Output result

A

0

1

0

1

1

=11

B

────────

=

0

1

1

1

=3

💡 Final answer: 3 set bits

Algorithm complete

A

0

1

0

1

1

=11

B

────────

=

0

1

1

1

=3

💡 Algorithm finished with correct count

Key Takeaways

✓ The algorithm counts the number of '1' bits by converting the number to a binary string and counting '1's.

This insight is hard to see from code alone because the conversion and counting happen in a single line, but the visualization shows each bit checked.

✓ Only bits set to '1' increment the count; zero bits are ignored.

Seeing the bits individually helps understand why zeros do not affect the count.

✓ The final count corresponds exactly to the number of set bits in the input number.

The visualization links the binary input to the numeric output, clarifying the relationship.

Practice

1. Given the following Python code, what is the output of isPowerOfFour(16)?

easy

A. True

B. False

C. Raises an error due to floating point precision

D. None

Solution

1. Step 1: Calculate log2(16)

   log2(16) = 4, dividing by 2 gives 2.0.

2. Step 2: Check if 2.0 equals int(2.0)

   2.0 == 2 is True, so the function returns True.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   16 is 4^2, so output True is expected [OK]

Hint: log2(16)/2 = 2.0 equals int(2) -> True

Common Mistakes:

• Assuming floating point error causes failure
• Confusing power of two with power of four

2. What is the time complexity of the Brian Kernighan's bit counting trick approach when counting set bits for all numbers from 0 to n?

medium

A. O(n * k) where k is the average number of set bits per number

B. O(n) because each number is processed in constant time

C. O(n * log n) because each number requires checking all bits

D. O(n^2) due to nested loops over bits and numbers

Solution

1. Step 1: Identify loops and operations

   Outer loop runs n+1 times; inner loop runs as many times as set bits in each number.

2. Step 2: Analyze average inner loop iterations

   Each iteration clears one set bit, so total inner loop iterations over all numbers is proportional to total set bits, roughly n * k.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Counting bits per number depends on number of set bits, not all bits [OK]

Hint: Time depends on total set bits, not total bits [OK]

Common Mistakes:

• Assuming O(n log n) because of bit length
• Thinking each number is constant time
• Confusing nested loops as quadratic

3. What is the time and space complexity of the optimal bitwise FSM solution for the Single Number II problem?

medium

A. Time: O(n), Space: O(1)

B. Time: O(n), Space: O(n)

C. Time: O(n^2), Space: O(1)

D. Time: O(n log n), Space: O(n)

Solution

1. Step 1: Identify complexity of outer and inner loops

   The algorithm iterates once over the input array (n elements), performing constant time bitwise operations per element.

2. Step 2: Check if recursion stack adds extra space

   No recursion or extra data structures are used; only fixed variables 'ones' and 'twos' consume constant space.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Linear time and constant space confirmed by single pass and fixed variables [OK]

Hint: Bitwise FSM uses fixed variables, no extra data structures [OK]

Common Mistakes:

• Assuming sorting or hash map space/time
• Confusing bit operations cost

4. Consider this buggy code snippet for finding two unique numbers. Which line contains the subtle bug?

medium

A. Line 8: set_bit calculation

B. Line 6: xor calculation loop

C. Line 3: xor initialization

D. Line 12: partitioning condition

Solution

1. Step 1: Identify how set_bit is computed

   Correct approach uses set_bit = xor & (-xor) to isolate rightmost set bit. Here, set_bit = xor misses this step.

2. Step 2: Understand impact of bug

   Without isolating rightmost set bit, partitioning fails, XOR groups won't separate unique numbers correctly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bug in set_bit calculation breaks partitioning [OK]

Hint: Isolate rightmost set bit with xor & (-xor) [OK]

Common Mistakes:

• Using xor directly as set_bit
• Breaking early before full XOR
• Misusing partition condition

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