Given an unsigned integer, return how many of its bits are 1. This count is also called the Hamming weight.
DSA Animator › DSA Revision › Bit Manipulation › Number of 1 Bits
Remember: n AND n minus 1 removes the lowest set bit. This trick appears in many bit problems. The video solves Number of 1 Bits (LeetCode 191, Easy) with the Brian Kernighan pattern from the Bit Manipulation topic, and you can replay every step in the interactive Number of 1 Bits animation.
Given an unsigned integer, return how many of its bits are 1. This count is also called the Hamming weight.
For 11, which is 1011 in binary, the answer is 3.
You can check all 32 bits one by one with a shift and a mask. That always takes 32 steps, even when only a few bits are set.
Look at n minus 1 in binary: the lowest 1 bit of n turns into 0, and every bit below it turns into 1. So n AND n minus 1 is n with its lowest set bit removed. Repeat until n becomes 0, counting each step. The loop runs exactly once per 1 bit.
n is 1011. n minus 1 is 1010, and the AND is 1010, so the count is 1. Next, 1010 AND 1001 is 1000, and the count is 2. Then 1000 AND 0111 is 0, and the count is 3. n is now 0, so the answer is 3.
In code, set count to 0. While n is not 0, set n to n AND n minus 1, and add one to count. Return count, so it's O of the number of set bits.
Remember: n AND n minus 1 removes the lowest set bit. This trick appears in many bit problems.