Number of 1 Bits

AS
Ackshaey Singh
Difficulty Easy
Time Complexity
O(number of bits in n)
Space Complexity
O(1)
Bit manipulation Divide and conquer
Box Apple Meta Bloomberg Adobe Yahoo Google Amazon Microsoft Uber Cisco Nvidia Qualcomm AMD

You are in a technical screen at Apple, and the interviewer opens a shared coding environment. "Given a non-negative integer, count the number of 1 bits in its binary representation." It sounds straightforward, but this problem tests 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 once you solve the first part.

TL;DR

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

Why This Problem Matters

Bit manipulation separates candidates who memorize solutions from those who 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 become much more approachable.

Binary Representation: A Quick Primer

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

Here are some examples:

DecimalBinarySet Bits
1110113
128100000001
255111111118
000

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

Understanding the Problem

Given: A non-negative integer n Return: The number of 1 bits in the binary representation of n Constraint: 0 <= n <= 2^31 - 1, so n fits in a signed 32-bit integer

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.

For n = 128, the binary form is 10000000. Only one bit is set, so the answer is 1.

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, the largest input allowed

Solution Approach

The strategy is to inspect each bit position, check whether it is a 1 or a 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. 1 in binary is 0...001, so every bit position except the last becomes zero.

Loading visualization...

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 reading 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.

Loading visualization...

Each shift divides the number by 2 and drops 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)
    • Shift n right by 1
  3. Return count

Here is the full trace for n = 11:

Loading visualization...

The algorithm processes four bits (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:

Loading visualization...

Implementation

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

public class Solution {

  /**
   * Calculates the number of set bits (1s) in the binary representation of a given integer.
   *
   * @param n The positive integer whose set bits are to be counted.
   * @return The number of set bits in the binary representation of the integer.
   */
  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:

  • The signed shift >> is safe here: Java's int is a signed 32-bit integer, and >> copies the sign bit into the top position on every shift. The constraint 0 <= n <= 2^31 - 1 means the sign bit of n is always 0. Each shift fills the top with 0, the value shrinks toward 0, and the loop ends.
  • count += n & 1: This is cleaner than an if-statement. The expression is either 0 or 1, so adding it directly acts as a conditional increment.
  • Loop termination: The loop ends when n becomes 0, which means every 1 bit has been shifted out. The largest input has 31 bits, so the loop runs at most 31 times.

Step-by-Step Trace

For n = 11 (binary 1011):

Iterationn (binary)n & 1countn after shift
1101111101
21011210
310021
41130

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

Complexity Analysis

Time Complexity: O(number of bits in n)

The loop runs once per bit of n, from the lowest bit up to the highest set bit. A positive n has floor(log2(n)) + 1 bits. The constraint caps n at 2^31 - 1, so the loop runs at most 31 times. When n = 0, it does not run at all.

Space Complexity: O(1)

The algorithm uses one counter, whatever the size of n. No additional data structures are needed.

The Brian Kernighan Optimization

A well-known follow-up is attributed to Brian Kernighan (of K&R C fame). Instead of checking every bit position, you can jump straight 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 every bit from the lowest set bit downward. ANDing with the original n zeroes out that lowest set bit and leaves every bit above it unchanged.

Loading visualization...

The loop body becomes n &= n - 1 followed by count++, and the loop still stops when n reaches 0. For n = 11 (binary 1011), this takes 3 iterations (one per set bit) instead of 4 (one per bit position). The gap grows for sparse numbers. For n = 128 (binary 10000000), the shift loop takes 8 iterations, while Kernighan's trick finishes in 1.

The time complexity becomes O(k), where k is the number of set bits. When every bit is set, k equals the number of bits in n, so the worst case matches the shift loop.

When to Use Which Approach

Loading visualization...

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

Common Pitfalls

  1. Assuming >> loops forever: Arithmetic right shift copies the sign bit, so a negative number never reaches 0 under >>. That only matters when the sign bit can be 1. Here the constraint keeps n between 0 and 2^31 - 1, so the sign bit is always 0 and >> terminates. If a variant allows negative input or treats the value as an unsigned 32-bit pattern, switch to >>> in Java and JavaScript.

  2. Using a fixed iteration count: Some candidates loop exactly 32 times (for example, for i in range(32)). This works, but it processes zero bits above the highest set bit. The while n != 0 condition stops as soon as no 1 bits remain.

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

  4. Forgetting the zero case: If n = 0, the while loop never executes and count stays at 0, which is correct. Check that your solution returns 0 for this input.

Interview Tips

When this problem comes up in an interview:

  1. Clarify the input range: Ask whether the input can be negative. The constraint 0 <= n <= 2^31 - 1 rules that out, which is why a signed shift works. Some variants treat the input as an unsigned 32-bit value, and those need an unsigned shift.

  2. Start with the loop-and-shift approach: It is the most direct correct solution. Write it, trace through an example, and state 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 number of set bits." 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 a pattern-based approach)
    • "How would you reverse the bits of an integer?" (A similar loop that shifts in both directions)
  5. Know your language's shift operators: Java and JavaScript have both >> and >>>. Python and Ruby integers have arbitrary precision, so >> works for any non-negative value. In C++ and C#, >> on a signed int is safe here because the input is never negative.

Key Takeaways

  • The n & 1 operation extracts the least significant bit, and n >>= 1 moves to the next bit. Together they form the standard bit-inspection loop.
  • The loop runs once per bit of n, so the time is O(number of bits in n), at most 31 iterations under the constraint. Space is O(1).
  • The constraint 0 <= n <= 2^31 - 1 keeps the sign bit at 0, so the signed shift >> is safe in every language. The unsigned shift >>> is only needed if negative input is allowed.
  • Brian Kernighan's trick (n &= n - 1) clears the lowest set bit each iteration and reduces the loop count to O(k), where k is the number of set bits.
  • 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.

Practice Makes Perfect

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

  • Reverse the 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 prepared for technical interviews and gone on to receive offers at top tech companies. Bit manipulation can feel tricky at first, but steady practice with problems like this one builds the intuition you need for any bitwise question.

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 to worry about. The >> operator works for every non-negative input.

class Solution:
    """
    Calculates the number of set bits (1s) in the binary representation of a given integer.

    :param int n: A positive integer whose set bits are to be counted.
    :return: The number of set bits in the binary representation of the integer.
    :rtype: int
    """
    def hamming_weight(self, n: int) -> int:
        count = 0
        while n != 0:
            count += n & 1
            n >>= 1
        return count

JavaScript

JavaScript converts numbers to 32-bit signed integers for bitwise operations. The input is never negative, so the signed shift >> always fills the top bit with 0 and the loop ends.

class Solution {
  /**
   * Calculates the number of set bits (1s) in the binary representation of a number.
   *
   * @param {number} n - The positive integer whose set bits are to be counted.
   * @returns {number} - The number of set bits in the binary representation of n.
   */
  hammingWeight(n) {
    let count = 0;
    while (n !== 0) {
      count += n & 1;
      n >>= 1;
    }
    return count;
  }
}

module.exports = Solution;

TypeScript

The TypeScript version matches the JavaScript one, with type annotations on the parameter and return value.

class Solution {
  /**
   * Calculates the number of set bits (1s) in the binary representation of a number.
   *
   * @param n - The positive integer whose set bits are to be counted.
   * @returns The number of set bits in the binary representation of n.
   */
  hammingWeight(n: number): number {
    let count = 0;
    while (n !== 0) {
      count += n & 1;
      n >>= 1;
    }
    return count;
  }
}

export { Solution };

C++

The solution uses a signed int. Right shift on a non-negative int fills with zeros, and the constraint guarantees n is never negative.

#include "HelperFuncs.h"
#include <vector>

class Solution {
public:
  /**
   * Calculates the number of set bits (1s) in the binary representation of a given integer.
   *
   * @param n The positive integer whose set bits are to be counted.
   * @return The number of set bits in the binary representation of n.
   */
  int hammingWeight(int n) {
    int count = 0;
    while (n != 0) {
      count += n & 1;
      n >>= 1;
    }
    return count;
  }
};

Go

Go has no >>> operator. The >> operator on a signed int is safe here because the constraint guarantees non-negative input.

package solution

// HammingWeight returns the number of set bits (1s) in the binary representation of a given integer n.
//
// Parameters:
//   - n: A positive integer whose set bits are to be counted.
//
// Returns:
//   - An integer representing the number of set bits in the binary representation of n.
func (s *Solution) HammingWeight(n int) int {
    count := 0
    for n != 0 {
        count += n & 1
        n >>= 1
    }
    return count
}

// Solution is required to run your method. Do not modify.
type Solution struct {
}

Scala

Scala parameters are immutable, so the solution copies n into a var. The signed shift >>= is safe because the input is non-negative.

class Solution {
  /**
   * Returns the number of set bits (1s) in the binary representation of the given integer.
   *
   * @param n A positive integer whose set bits are to be counted.
   * @return The number of set bits in the binary representation of n.
   */
  def hammingWeight(n: Int): Int = {
    var count = 0
    var num = n
    while (num != 0) {
      count += num & 1
      num >>= 1
    }
    count
  }
}

Kotlin

Kotlin uses the infix functions and for bitwise AND and shr for signed right shift. shr is safe here because the input is non-negative.

class Solution {
    /**
     * Calculates the number of set bits (1s) in the binary representation of a given integer.
     *
     * @param n The positive integer whose set bits are to be counted.
     * @return The number of set bits in the binary representation of the integer.
     */
    fun hammingWeight(n: Int): Int {
        var count = 0
        var num = n
        while (num != 0) {
            count += num and 1
            num = num shr 1
        }
        return count
    }
}

Swift

Swift parameters are constants, so the solution creates a mutable copy with var. The >> operator works for non-negative Int values.

class Solution {
    /**
     * Calculates the number of set bits (1s) in the binary representation of a given integer.
     *
     * - Parameter n: The positive integer whose set bits are to be counted.
     * - Returns: The number of set bits in the binary representation of the integer.
     */
    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's, so right shift works for any non-negative input.

class Solution
  # Calculates the number of set bits (1s) in the binary representation of a given integer.
  #
  # @param n [Integer] The positive integer whose set bits are to be counted
  # @return [Integer] The number of set bits in the binary representation of the integer
  def hamming_weight(n)
    count = 0
    while n != 0
      count += n & 1
      n >>= 1
    end
    count
  end
end

Rust

The solution copies n into a mutable i32 and shifts it with >>=. On a signed type this is an arithmetic shift, which is safe because the input is never negative.

pub struct Solution;

impl Solution {
    /// Calculates the number of set bits (1s) in the binary representation of a given integer.
    ///
    /// # Arguments
    /// * `n` - The positive integer whose set bits are to be counted
    ///
    /// # Returns
    /// The number of set bits in the binary representation of the integer
    pub fn hamming_weight(&self, n: i32) -> i32 {
        let mut count = 0;
        let mut num = n;
        while num != 0 {
            count += num & 1;
            num >>= 1;
        }
        count
    }
}

C#

C# follows the same pattern as Java. The signed shift >>= on an int is safe because the input is non-negative.

public class Solution {
    /// <summary>
    /// Calculates the number of set bits (1s) in the binary representation of a given integer.
    /// </summary>
    /// <param name="n">The positive integer whose set bits are to be counted.</param>
    /// <returns>The number of set bits in the binary representation of the integer.</returns>
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            count += n & 1;
            n >>= 1;
        }
        return count;
    }
}

Dart

Dart's int is a 64-bit signed integer on native platforms. The input is non-negative, so >>= always shifts in zeros.

class Solution {
  /// Calculates the number of set bits (1s) in the binary representation of a given integer.
  ///
  /// [n] The positive integer whose set bits are to be counted.
  /// Returns the number of set bits in the binary representation of the integer.
  int hammingWeight(int n) {
    int count = 0;
    while (n != 0) {
      count += n & 1;
      n >>= 1;
    }
    return count;
  }
}

PHP

PHP integers are signed, but >> works for every non-negative value in the constraint range.

<?php

class Solution {
    /**
     * Calculates the number of set bits (1s) in the binary representation of a given integer.
     *
     * @param int $n The positive integer whose set bits are to be counted.
     * @return int The number of set bits in the binary representation of the integer.
     */
    public function hammingWeight(int $n): int {
        $count = 0;
        while ($n != 0) {
            $count += $n & 1;
            $n >>= 1;
        }
        return $count;
    }
}

Frequently Asked Questions

What is Hamming weight and how does it relate to counting set bits?
Hamming weight is the number of non-zero symbols in a string. For binary integers, it equals the count of 1 bits. The terms Hamming weight, popcount (population count), and number of 1 bits all refer to the same thing. This concept is used in error detection, cryptography, and information theory.
What is the time complexity of counting set bits using the loop and shift approach?
The time complexity is O(number of bits in n). The loop runs once per bit, shifting right each time until the value reaches zero. A positive n has floor(log2(n)) + 1 bits. The constraint caps n at 2^31 - 1, so the loop runs at most 31 times. When n is 0, it does not run at all.
What is Brian Kernighan's bit counting trick and why is it faster?
Brian Kernighan's trick uses n & (n - 1) to clear the lowest set bit in each iteration. The loop runs exactly k times, where k is the number of set bits, instead of once per bit position. For a sparse number like 128 (one set bit), it finishes in one iteration instead of eight.
Why does n & 1 isolate the least significant bit?
The number 1 in binary is 0...001, with only the rightmost bit set. Bitwise AND returns 1 only in positions where both operands have a 1. Every bit of 1 except the last is zero, so n & 1 clears everything except the least significant bit of n.
What is the difference between logical right shift and arithmetic right shift?
Logical right shift (>>> in Java and JavaScript) always fills the leftmost bit with 0. Arithmetic right shift (>>) copies the sign bit into the leftmost position, so a negative number keeps shifting in 1s. For a non-negative number the sign bit is 0, and the two shifts give the same result.
Why is the signed shift >> safe in Java and JavaScript for this problem?
The constraint keeps n between 0 and 2^31 - 1, so n always fits in a signed 32-bit integer with its sign bit set to 0. Arithmetic right shift copies that 0 into the top position on every shift. The value keeps shrinking until it reaches 0, and the loop ends. A negative input would need the unsigned shift >>>, but the constraints rule that case out.
Can you count set bits without a loop using built-in functions?
Yes. Java has Integer.bitCount(n), Python has bin(n).count('1'), C++ has __builtin_popcount(n), and Go has math/bits.OnesCount(). These often compile to a hardware POPCNT instruction and run in O(1). Interviewers usually want you to write the counting logic yourself to show you understand bitwise operations.
How does the set bit count relate to powers of two?
A power of two has exactly one set bit in its binary representation (for example, 8 = 1000 and 64 = 1000000). You can check whether a number is a power of two by testing whether its Hamming weight equals 1. A faster check is n > 0 and n & (n - 1) == 0. This property is used in memory alignment checks and hash table sizing.
What are practical applications of counting set bits?
Counting set bits is used in network subnet masking (the count of 1s in a subnet mask gives the CIDR prefix length), error-correcting codes (the Hamming distance between two values is the popcount of their XOR), chess engines (counting pieces on a bitboard), database bitmap indexes (counting matching records), and cryptographic hash evaluation.
How does this problem appear in coding interviews at major tech companies?
Companies like Apple, Meta, Google, and Bloomberg use this problem as a warm-up or as part of a larger bit manipulation question. Common follow-ups include counting total set bits from 1 to n, finding the Hamming distance between two numbers, and reversing the bits of an integer. Knowing both the loop-and-shift approach and Brian Kernighan's trick shows solid bit manipulation fluency.