Scale Engineer

Number of 1 Bits

Easy
#0181Time: O(k), where k is the number of bits in the integer (e.g., 32). Since k is a constant, this is technically O(1), but it performs a fixed number of iterations regardless of the input's properties.Space: O(1)5 companies
Patterns
Bit Manipulation
Algorithms
Divide and Conquer
Companies
AMDCiscoQualcommVerkada

Prompt

Given a positive integer n, write a function that returns the number of set bits in its binary representation (also known as the Hamming weight).

 

Example 1:

Input: n = 11

Output: 3

Explanation:

The input binary string 1011 has a total of three set bits.

Example 2:

Input: n = 128

Output: 1

Explanation:

The input binary string 10000000 has a total of one set bit.

Example 3:

Input: n = 2147483645

Output: 30

Explanation:

The input binary string 1111111111111111111111111111101 has a total of thirty set bits.

 

Constraints:

  • 1 <= n <= 231 - 1

 

Follow up: If this function is called many times, how would you optimize it?

Approaches

3 approaches with complexity analysis and trade-offs.

This is a straightforward approach where we iterate through each of the 32 bits of the integer. In each iteration, we check if the current bit is a '1' and shift the number to the right to process the next bit.

Algorithm

  • Initialize a counter count to zero.
  • Loop 32 times, as we are dealing with 32-bit integers.
  • Inside the loop, use a bitmask 1 to check the least significant bit (LSB) of the number n. The expression (n & 1) will be 1 if the LSB is 1, and 0 otherwise.
  • Add the result of this check to count.
  • Right-shift the number n by one position (n >>= 1) to move the next bit into the LSB position for the next iteration.
  • After 32 iterations, count will hold the total number of set bits.

Walkthrough

This approach iterates through all 32 bits of the integer. The algorithm is as follows:

  • Initialize a counter count to zero.
  • Loop 32 times. In each iteration, we check the least significant bit (LSB).
  • The check is done using a bitwise AND with 1: (n & 1). If the result is 1, it means the LSB is a set bit, and we increment count.
  • After checking the bit, we shift the number n one position to the right (n >>= 1) to expose the next bit at the LSB position for the subsequent iteration.
  • After the loop completes, count holds the total number of set bits.
public class Solution {    // you need to treat n as an unsigned value    public int hammingWeight(int n) {        int count = 0;        for (int i = 0; i < 32; i++) {            if ((n & 1) == 1) {                count++;            }            // Using unsigned right shift is safer for negative numbers,            // but for the given constraints (positive n), >> is fine.            n = n >> 1;        }        return count;    }}

Complexity

Time

O(k), where k is the number of bits in the integer (e.g., 32). Since k is a constant, this is technically O(1), but it performs a fixed number of iterations regardless of the input's properties.

Space

O(1)

Trade-offs

Pros

  • Simple to understand and implement.

Cons

  • Performs a fixed number of iterations (32), which is inefficient for numbers with few set bits (e.g., n=1).

Solutions

public class Solution { // you need to treat n as an unsigned value public int hammingWeight ( int n ) { int ans = 0 ; while ( n != 0 ) { n &= n - 1 ; ++ ans ; } return ans ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem