Counting Set Bits in Binary Representation

You're sitting in a technical screen at Apple when the interviewer pulls up a shared coding environment. "Given an integer, count the number of 1-bits in its binary representation." It sounds straightforward, but this problem is a litmus test for how comfortable you are with bitwise operations. It shows up regularly at companies like Box, Meta, Bloomberg, and Google, and the follow-up questions can get surprisingly deep if you nail the initial solution.

TL;DR

Use a loop that checks the least significant bit with n & 1, adds it to a counter, and then right-shifts n by one position. Repeat until n reaches zero. The counter holds the Hamming weight. This runs in O(log n) time and O(1) space. For an optimized variant, Brian Kernighan's trick (n &= n - 1) clears the lowest set bit each iteration, running in O(k) time where k is the number of set bits.

Why This Problem Matters

Bit manipulation is one of those topics that separates candidates who memorize solutions from those who genuinely understand how computers represent data. Counting set bits is the entry point into this category. Once you understand how &, >>, and >>> work together, problems like single number detection, power-of-two checks, and Hamming distance calculations become much more approachable.

Binary Representation: A Quick Primer

Every integer is stored as a sequence of bits (0s and 1s) in memory. A "set bit" simply means a bit whose value is 1. The count of set bits is called the Hamming weight or population count (popcount).

Here are the examples from the problem:

The rightmost bit is the least significant bit (LSB), and the leftmost is the most significant bit (MSB). Our algorithm will process bits from right to left, examining one bit at a time.

Understanding the Problem

Given: A positive integer n Return: The number of 1-bits in the binary representation of n Constraint: 1 <= n <= 2^31 - 1

For n = 11, the binary form is 1011. Reading right to left: bit 0 is 1, bit 1 is 1, bit 2 is 0, bit 3 is 1. Three bits are set, so the answer is 3.

Edge Cases

1. n = 0: Zero set bits (binary 0)
2. n = 1: One set bit (binary 1)
3. n = 255: Eight set bits (binary 11111111)
4. n = 2147483647 (2^31 - 1): Thirty-one set bits (all 1s in a 31-bit representation)

Solution Approach

The strategy is to inspect each bit position, check whether it's a 1 or 0, and keep a running count. Two bitwise operations make this possible.

How n & 1 Extracts the Least Significant Bit

The bitwise AND between n and 1 isolates the rightmost bit. Since 1 in binary is 0...001, every bit position except the last gets zeroed out.

When n = 11 (binary 1011), n & 1 yields 1 because the LSB is set. When n = 10 (binary 1010), n & 1 yields 0 because the LSB is not set.

How Right Shift Moves to the Next Bit

After inspecting the current LSB, we shift all bits one position to the right. The old LSB is discarded, and the next bit moves into the LSB position.

Each shift effectively divides the number by 2 (dropping the remainder). Once n reaches 0, every bit has been examined.

Building the Algorithm

Putting these two operations together:

1. Initialize count = 0
2. While n is not zero:
   • Add n & 1 to count (this is 1 if the LSB is set, 0 otherwise)
   • Right-shift n by 1
3. Return count

Here is the full trace for n = 11:

The algorithm processes four bits (since 11 in binary is 1011), finds three of them set, and returns 3.

For n = 128 (binary 10000000), the first seven iterations all find n & 1 == 0. Only the eighth iteration finds the single set bit:

Implementation

Prefer a different language? Jump to solutions in other languages.

public class Solution {
  public int hammingWeight(int n) {
    int count = 0;
    while (n != 0) {
      count += n & 1;
      n >>>= 1;
    }
    return count;
  }
}

A few things to notice about the Java implementation:

• >>> instead of >>: Java uses signed 32-bit integers. The >>> operator is an unsigned right shift that always fills the leftmost bit with 0. If we used >> (arithmetic right shift) on a number with the sign bit set, it would shift in 1s forever, causing an infinite loop.
• count += n & 1: This is cleaner than an if-statement. The expression evaluates to either 0 or 1, so adding it directly works as a conditional increment.
• Loop termination: The loop ends when n becomes 0, meaning all bits have been shifted out. For a 32-bit integer, this happens in at most 32 iterations.

Step-by-Step Trace

For n = 11 (binary 1011):

The loop runs 4 times (the number of bits in 11), and we find 3 set bits.

Complexity Analysis

Time Complexity: O(log n)

The number of bits in n is floor(log2(n)) + 1. The loop iterates once per bit, so it runs O(log n) times. For a 32-bit integer, this is at most 32 iterations, which is effectively constant for fixed-width integers.

Space Complexity: O(1)

Only a single counter variable is used, regardless of the size of n. No additional data structures are needed.

The Brian Kernighan Optimization

There is a well-known optimization attributed to Brian Kernighan (of K&R C fame). Instead of checking every bit position, you can skip directly to the next set bit.

The trick relies on one observation: n & (n - 1) clears the lowest set bit of n. Subtracting 1 from n flips all bits from the lowest set bit downward. ANDing with the original n zeroes out that lowest set bit while leaving everything above it untouched.

For n = 11 (binary 1011), this approach takes only 3 iterations (one per set bit) instead of 4 (one per bit position). The difference is more dramatic for sparse numbers. For n = 128 (binary 10000000), the standard approach takes 8 iterations while Kernighan's trick finishes in just 1.

public int hammingWeight(int n) {
    int count = 0;
    while (n != 0) {
        n &= (n - 1);
        count++;
    }
    return count;
}

The time complexity becomes O(k) where k is the number of set bits. In the worst case (all bits set), this is still O(log n), but for sparse inputs it is significantly faster.

When to Use Which Approach

The loop-and-shift approach is the standard interview answer. It is simple, correct, and easy to explain. Mentioning Brian Kernighan's trick as a follow-up demonstrates deeper knowledge of bit manipulation. Built-in functions like Integer.bitCount() in Java or __builtin_popcount() in C++ use hardware POPCNT instructions and run in O(1), but interviewers will ask you to implement the logic yourself.

Common Pitfalls

1. Using >> instead of >>> in Java/JavaScript: Arithmetic right shift preserves the sign bit. For inputs where the highest bit is set, >> shifts in 1s indefinitely, creating an infinite loop. Always use unsigned right shift (>>>) in languages with signed integers.

2. Forgetting the loop terminates: Some candidates add a fixed iteration count (e.g., for i in range(32)). While this works, it processes unnecessary zero bits. The while n != 0 condition is both cleaner and more efficient.

3. Converting to a string first: Calling something like Integer.toBinaryString(n).chars().filter(c -> c == '1').count() works but allocates a string and iterates through characters. Interviewers expect a bitwise solution for this problem.

4. Not handling the zero case: If n = 0, the while loop never executes and count stays at 0, which is correct. But double-check your solution handles this edge case properly.

Interview Tips

When this problem comes up in an interview:

1. Clarify the input range: Ask whether the input can be negative. The constraint 1 <= n <= 2^31 - 1 means non-negative, but in some variants the input is treated as an unsigned 32-bit value.

2. Start with the loop-and-shift approach: It is the simplest correct solution. Write it, trace through an example, and confirm the complexity.

3. Mention Kernighan's trick as a follow-up: After presenting the basic solution, say "There's an optimization using n & (n - 1) that runs in O(k) time where k is the set bit count." This shows breadth of knowledge.

4. Be ready for follow-ups:

   • "How would you find the Hamming distance between two numbers?" (XOR them, then count set bits)
   • "How would you count total set bits from 1 to n?" (Digit DP or pattern-based approach)
   • "How would you reverse the bits of an integer?" (Similar loop with shifting in both directions)

5. Know your language's shift operators: Java and JavaScript have both >> and >>>. Python handles arbitrary-precision integers, so >> always works. C++ uses >> for unsigned types. Getting this wrong causes subtle bugs.

Key Takeaways

• The n & 1 operation extracts the least significant bit, and right-shifting (n >>= 1 or n >>>= 1) advances to the next bit. Together, they form the standard bit-inspection loop.
• Brian Kernighan's trick (n &= n - 1) clears the lowest set bit each iteration, reducing the loop count from O(log n) to O(k) where k is the number of set bits.
• In Java and JavaScript, always use unsigned right shift (>>>) to avoid infinite loops caused by sign-bit propagation with arithmetic right shift (>>).
• This problem is a gateway to the broader bit manipulation category. The same &, >>, and ^ patterns reappear in problems like single number, power of two, and Hamming distance.
• For a 32-bit integer the loop runs at most 32 times, so in practice the time complexity is bounded by a small constant. Interviewers care more about your understanding of the bitwise mechanics than raw performance.

Practice Makes Perfect

Once you are comfortable counting set bits, try these related problems to build on your bit manipulation skills:

• Reverse bits of an integer (same loop structure, different accumulation)
• Check if a number is a power of two (single set bit check)
• Find the single number in an array (XOR all elements)
• Calculate the Hamming distance between two integers (XOR then count set bits)

This problem and thousands of others are available on Firecode, where over 50,000 users have successfully prepared for technical interviews and landed offers at top tech companies. Bit manipulation might feel tricky at first, but consistent practice with problems like this one builds the intuition you need to handle any bitwise question confidently.

Happy coding, and may all your bits be set in the right places!

Solutions in Other Languages

Python

Python integers have arbitrary precision, so there is no sign-bit issue. The standard >> operator works correctly for all non-negative inputs.

class Solution:
    def hamming_weight(self, n: int) -> int:
        count = 0
        while n:
            count += n & 1
            n >>= 1
        return count

JavaScript

JavaScript uses 32-bit signed integers for bitwise operations. Like Java, use >>> (unsigned right shift) to avoid sign-bit propagation.

class Solution {
  hammingWeight(n) {
    let count = 0;
    while (n !== 0) {
      count += n & 1;
      n >>>= 1;
    }
    return count;
  }
}

TypeScript

class Solution {
  hammingWeight(n: number): number {
    let count = 0;
    while (n !== 0) {
      count += n & 1;
      n >>>= 1;
    }
    return count;
  }
}

C++

C++ right shift on unsigned types fills with zeros. The solution uses int here, and >> works correctly for non-negative values within the constraint range.

class Solution {
public:
  int hammingWeight(int n) {
    int count = 0;
    while (n) {
      count += n & 1;
      n >>= 1;
    }
    return count;
  }
};

Go

Go does not have a >>> operator. The >> operator on int (which is signed) works correctly here since the constraint guarantees non-negative input.

func (s *Solution) HammingWeight(n int) int {
    count := 0
    for n != 0 {
        count += n & 1
        n >>= 1
    }
    return count
}

Scala

Scala inherits Java's >>> operator for unsigned right shift. The solution uses a mutable copy since function parameters are immutable in Scala.

class Solution {
  def hammingWeight(n: Int): Int = {
    var count = 0
    var num = n
    while (num != 0) {
      count += num & 1
      num >>>= 1
    }
    count
  }
}

Kotlin

Kotlin uses ushr for unsigned right shift and and for bitwise AND (infix functions rather than operators).

class Solution {
    fun hammingWeight(n: Int): Int {
        var count = 0
        var num = n
        while (num != 0) {
            count += num and 1
            num = num ushr 1
        }
        return count
    }
}

Swift

Swift parameters are constants by default, so a mutable copy is created with var. The >> operator works correctly for non-negative Int values.

class Solution {
    func hammingWeight(_ n: Int) -> Int {
        var count = 0
        var num = n
        while num != 0 {
            count += num & 1
            num >>= 1
        }
        return count
    }
}

Ruby

Ruby integers have arbitrary precision (like Python), so right shift always works correctly without sign-bit concerns.

class Solution
  def hamming_weight(n)
    count = 0
    while n != 0
      count += n & 1
      n >>= 1
    end
    count
  end
end

Rust

Rust requires explicit casting between signed and unsigned types. The solution casts to u32 for the right shift to ensure unsigned behavior, then casts back.

impl Solution {
    pub fn hamming_weight(&self, n: i32) -> i32 {
        let mut count = 0;
        let mut num = n;
        while num != 0 {
            count += num & 1;
            num = ((num as u32) >> 1) as i32;
        }
        count
    }
}

C#

C# supports >>> for unsigned right shift (added in C# 11). The solution follows the same pattern as Java.

public class Solution {
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            count += n & 1;
            n >>>= 1;
        }
        return count;
    }
}

Dart

Dart uses >>> for unsigned right shift, similar to Java and JavaScript.

class Solution {
  int hammingWeight(int n) {
    int count = 0;
    while (n != 0) {
      count += n & 1;
      n >>>= 1;
    }
    return count;
  }
}

PHP

PHP integers are signed, but >> works correctly for non-negative values within the constraint range.

class Solution {
    public function hammingWeight(int $n): int {
        $count = 0;
        while ($n != 0) {
            $count += $n & 1;
            $n >>= 1;
        }
        return $count;
    }
}