DSAPrep
EasyBit Manipulation

Number of 1 Bits

Given a positive integer n, write a function that returns the number of set bits in its binary representation (also known as the Hamming weight).

Example 1

Input: n = 11
Output: 3
Explanation: The input binary string 1011 has a total of three set bits.

Example 2

Input: n = 128
Output: 1
Explanation: The input binary string 10000000 has a total of one set bit.

Example 3

Input: n = 2147483645
Output: 30
Explanation: The input binary string 1111111111111111111111111111101 has a total of thirty set bits.

Constraints

  • 1 <= n <= 2^31 - 1
Follow-up: If this function is called many times, how would you optimize it?
View original on LeetCode ↗

The direct approach checks every one of the 32 bits. The clever trick uses the identity n & (n - 1), which clears the lowest set bit of n in a single operation — so the loop only runs once per set bit instead of once per bit position.

Check Every Bit

Time O(32) = O(1)Space O(1)

Shift through all 32 bit positions and test each one with a mask.

class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0
        for i in range(32):
            if n & (1 << i):
                count += 1
        return count

For n = 11 (binary 00000000000000000000000000001011), the loop tests bit 0 (1, set), bit 1 (1, set), bit 2 (0, clear), bit 3 (1, set), then bits 4 through 31 are all 0. Three bits are set, so it returns 3.

Complexity: always exactly 32 iterations regardless of how many bits are actually set → O(1) time (bounded by the fixed integer width), O(1) space.

Brian Kernighan's Trick

OptimalTime O(k)Space O(1)

n & (n - 1) always clears exactly the lowest set bit of n. Subtracting 1 flips every trailing zero to a 1 and the lowest set 1 to a 0; ANDing with the original n keeps all the higher bits untouched but zeroes out that lowest set bit. Repeating this until n becomes 0 counts each set bit exactly once, so the loop only runs k times where k is the number of set bits — never 32 regardless of how sparse the bits are.

class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0
        while n:
            n &= n - 1
            count += 1
        return count

Tracing n = 11:

n = 11  = 0b1011
n & (n-1) = 0b1011 & 0b1010 = 0b1010  (= 10)   count = 1
n & (n-1) = 0b1010 & 0b1001 = 0b1000  (= 8)    count = 2
n & (n-1) = 0b1000 & 0b0111 = 0b0000  (= 0)    count = 3
n == 0, stop → return 3

Complexity: the loop body runs once per set bit, so it takes O(k) time where k <= 32 is the number of set bits — strictly fewer iterations than checking all 32 positions whenever n is sparse. Still O(1) space.

Follow-up (called many times): precompute the Hamming weight of every byte (0–255) once into a 256-entry lookup table, then split n into four bytes and sum four table lookups. This amortizes the counting work across calls, turning each subsequent call into four O(1) array reads instead of a bit-by-bit loop.