Abstract / Summary

Count how many 1 bits are in the binary representation of a given number.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 77% (2+ million submissions).

Typical patterns to solve this problem:

• Bit Manipulation
• Divide And Conquer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a class Solution with a single public member function hammingWeight. The function receives a 32-bit unsigned integer and returns the count of bits set to 1 in its binary representation. The algorithm iteratively clears the least-significant set bit until the value becomes zero, incrementing a counter on each iteration. This approach yields the exact Hamming weight of the input value.

Key Steps

The core logic is expressed in a loop that runs while the input n is non-zero. The first statement inside the loop increments the result counter, reflecting the discovery of a set bit. The second statement applies the expression n &= n - 1, which removes the lowest set bit from n. After the loop terminates, the accumulated count is returned.

int result = 0;
while (n > 0)
{
    result++;
    n &= n - 1;
}
return result;

The initialization of result to zero establishes the starting count. The loop condition n > 0 guarantees that the body executes only when there remains at least one set bit. The increment operation result++ records the removal of a set bit. The bitwise operation n &= n - 1 is the pivotal step that transforms n by clearing its least-significant 1. Finally, the function returns the total number of cleared bits, which equals the Hamming weight.

Edge Cases

When the input value n is zero, the loop condition fails immediately, and the function returns the initial value of result, which is zero. This correctly represents the fact that a zero value contains no set bits. For the maximum possible 32-bit unsigned integer (0xFFFFFFFF), the loop iterates exactly 32 times, each iteration clearing one bit, and the final result is 32. The algorithm therefore handles both the lower bound (no bits set) and the upper bound (all bits set) without special-case code.

Performance Optimizations

The use of n &= n - 1 is a classic bit-twiddling technique that reduces the number of loop iterations to the number of set bits rather than the total number of bits in the word. Consequently, the runtime scales with the sparsity of the input: inputs with few 1s complete quickly, while dense inputs require more iterations but never exceed 32 cycles for a 32-bit integer. This eliminates the need for a fixed-size iteration over each bit position and avoids unnecessary conditional checks for each bit. The algorithm also operates entirely with registers and simple arithmetic, ensuring minimal overhead.

Imagine that every number is made up of a long row of tiny light bulbs that are either turned on or turned off. Computers see numbers as these rows of lights. A light that is on is like the number one, and a light that is off is like the number zero.

This piece of code is on a treasure hunt to find out how many light bulbs are glowing brightly. It starts with a little counter set to zero. Then, it looks at the row of bulbs. Whenever it finds a bulb that is shining, it adds one to the counter.

To do this very quickly, the code uses a special trick. Every time it finds a light that is on, it magically turns that light off and moves on to find the next one. It keeps doing this over and over again until all the bulbs are dark. Once there are no more glowing lights left to find, the counter shows exactly how many lights were shining at the very beginning.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python	Java								TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java		C	JS	Go			Rust	TS
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	begeekmyfriend					C
	BigEggStudy				C#
	black-shadows	C++
	chandansgowda		Python
	charles-wangkai			Java
	chenyanzhe	C++
	Dijkstra-Edu			Java
	everthis						JS
	fartem								Ruby
	fengvyi	C++
	fpdjsns	C++
	gaosq0604		Python
	Garvit244		Python
	halfrost							Go
	haoel	C++
	JoshCrozier						JS
	keineahnung2345	C++
	Krazune	C++
	lennylxx					C
	linouk23	C++
	lkwq007		Python
	luangong	C++
	muhammadfarhankt							Go
	qiyuangong		Python
	shreymehul				C#
	sonugiri1043	C++
	suxrobGM				C#
	varunu28			Java
	vli02					C
	vthwang			Java
	XiaotaoGuo	C++
	yuanliu666									Kotlin
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C, C++, Go, Java, JavaScript, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
chandansgowda	Python
charles-wangkai	Java
chenyanzhe	C++
Dijkstra-Edu	Java
everthis	JavaScript
fartem	Ruby
fengvyi	C++
fpdjsns	C++
gaosq0604	Python
Garvit244	Python
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
lennylxx	C
linouk23	C++
lkwq007	Python
luangong	C++
muhammadfarhankt	Go
qiyuangong	Python
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
varunu28	Java
vli02	C
vthwang	Java
XiaotaoGuo	C++
yuanliu666	Kotlin
YuriSpiridonov	Python
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality