Number of 1 Bits

Return the number of 1 bits in the binary representation of a non-negative integer (its Hamming weight).

A way to picture it

Picture a row of light bulbs. n & (n − 1) is a magic switch that turns off exactly the rightmost bulb that's on. Count how many flicks it takes to plunge the room into darkness.

How to approach it

n & (n − 1) clears the lowest set bit. The loop runs once per 1 bit, not once per bit.

Example

Input: {"n":11}. Output: 3.

Complexity: O(k) time and O(1) space. k is the number of set bits — at most 32.

This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.