Number of 1 Bits

Given an integer, count how many of its binary bits are set to 1 (its "Hamming weight").

Example

Input: 11 (binary 1011) Output: 3

Approach

Repeatedly check the lowest bit with n & 1, add it to a running count, then right-shift n by one bit to check the next one. Stop once n becomes 0. This runs in O(number of bits) time — for a 32-bit integer, at most 32 iterations.

Walkthrough

1count = 0
2while n:
3    count += n & 1
4    n >>= 1
5print(count)

Input format

Line 1: a single non-negative integer n

Print the number of set bits.