Number of 1 Bits
Problem statement
Given a positive integer n, return how many 1 bits appear in its binary representation. This count is also called the Hamming weight or population count.
Examples
Example 1
Input: n = 13
Output: 3
Explanation: 13 in binary is 1101, which has three 1 bits.
Example 2
Input: n = 256
Output: 1
Explanation: 256 is 100000000: a single 1 followed by eight zeros.
Hints
Approach
Brian Kernighan's trick: n & (n - 1) removes the lowest set bit.
Subtracting one flips the lowest 1 to 0 and turns every 0 below it into 1. ANDing with the original keeps everything above that bit and zeroes the rest. For 12 (1100): 11 is 1011, and 1100 & 1011 = 1000.
- While
nis not zero, setn = n & (n - 1)and add one to the count. - Return the count.
The loop runs once per set bit, so 256 takes one iteration instead of 32.
O(k), k = number of 1 bitsSpace O(1)class Solution: def hammingWeight(self, n: int) -> int: count = 0 while n: n &= n - 1 # clear the lowest set bit count += 1 return countFollow-up questions
- You call this function millions of times. How could a precomputed 256-entry table for each byte speed it up?
- Given a dotted IPv4 netmask string, return its CIDR prefix length.
Frequently asked questions
Yes: n.bit_count() in Python 3.10+ (or bin(n).count("1")), and Integer.bitCount(n) in Java. Mention them, but interviewers usually want to see the bit manipulation.
Counting set bits is how you get the size of a network from a netmask: 255.255.255.0 has 24 one bits, so it is a /24. The same operation counts enabled flags in a permission bitmask, such as the bits in a Unix file mode.