Number of 1 Bits
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:
| Decimal | Binary | Set Bits |
|---|---|---|
| 11 | 1011 | 3 |
| 128 | 10000000 | 1 |
| 255 | 11111111 | 8 |
| 0 | 0 | 0 |
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
- n = 0: Zero set bits (binary
0) - n = 1: One set bit (binary
1) - n = 255: Eight set bits (binary
11111111) - 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:
- Initialize
count = 0 - While
nis not zero:- Add
n & 1tocount(this is 1 if the LSB is set, 0 otherwise) - Shift
nright by 1
- Add
- 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'sintis a signed 32-bit integer, and>>copies the sign bit into the top position on every shift. The constraint0 <= n <= 2^31 - 1means the sign bit ofnis 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
nbecomes 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):
| Iteration | n (binary) | n & 1 | count | n after shift |
|---|---|---|---|---|
| 1 | 1011 | 1 | 1 | 101 |
| 2 | 101 | 1 | 2 | 10 |
| 3 | 10 | 0 | 2 | 1 |
| 4 | 1 | 1 | 3 | 0 |
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
-
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 keepsnbetween 0 and2^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. -
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. Thewhile n != 0condition stops as soon as no 1 bits remain. -
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. -
Forgetting the zero case: If
n = 0, the while loop never executes andcountstays at 0, which is correct. Check that your solution returns 0 for this input.
Interview Tips
When this problem comes up in an interview:
-
Clarify the input range: Ask whether the input can be negative. The constraint
0 <= n <= 2^31 - 1rules 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. -
Start with the loop-and-shift approach: It is the most direct correct solution. Write it, trace through an example, and state the complexity.
-
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. -
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)
-
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 signedintis safe here because the input is never negative.
Key Takeaways
- The
n & 1operation extracts the least significant bit, andn >>= 1moves 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 - 1keeps 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;
}
}