Skip to main content

Counting Bits

Every problem here answers how many bits are set, not which ones. That single primitive - the popcount - is the whole page: x.bit_count() in Python 3.10+, or Kernighan's n &= n - 1 loop, which spins once per set bit instead of once per bit width.

Once you have the count, problems differ only in what they do with it: return it, sort by it, use its parity, or search for the numbers that produce a given one.

Popcount​

Count the 1s in a single number, or in every number up to n. The DP recurrence dp[i] = dp[i >> 1] + (i & 1) builds the whole table in one pass by reusing the answer for i without its lowest bit.

191. Number of 1 Bits​

Easy·
2 Approaches
FIG. 191 LSB● INTERACTIVE
visualization loads as you reach it
class Solution:
def hammingWeight(self, n: int) -> int:
"""Loop"""
bits = 0
while n != 0:
if n & 1: # Check if the least significant bit is set or not
bits += 1
n >>= 1
return bits

338. Counting Bits​

Easy·
3 Approaches
FIG. 338 COUNTING BITS LRU● INTERACTIVE
visualization loads as you reach it
class Solution:
def countBits(self, n: int) -> List[int]:
@lru_cache(maxsize=None)
def rec(i):
if i == 0:
return 0
return 1 + rec(i & (i - 1))
 
return [rec(i) for i in range(n + 1)]

2595. Number of Even and Odd Bits​

Easy·
FIG. 2595 NUMBER OF EVEN AND ODD BITS● INTERACTIVE
visualization loads as you reach it
class Solution:
def evenOddBit(self, n: int) -> List[int]:
even = odd = 0
pos = 0
while n != 0:
if n & 1: # Check if the least significant bit is set or not
if pos % 2:
odd += 1
else:
even += 1
pos += 1
n >>= 1
return [even, odd]

1356. Sort Integers by The Number of 1 Bits​

Easy·
class Solution:
def hammingWeight(self, n: int) -> int:
bits = 0
while n != 0:
n = n & (n - 1) # Unset the lowest set bit
bits += 1
return bits
 
def sortByBits(self, arr: List[int]) -> List[int]:
return sorted(arr, key=lambda i: (self.hammingWeight(i), i))

2859. Sum of Values at Indices With K Set Bits​

Easy·
FIG. 2859 SUM OF VALUES AT INDICES WITH K SET BITS● INTERACTIVE
visualization loads as you reach it
class Solution:
def hammingWeight(self, n: int) -> int:
bits = 0
while n != 0:
n = n & (n - 1) # Unset the lowest set bit
bits += 1
return bits
 
def sumIndicesWithKSetBits(self, nums: List[int], k: int) -> int:
total = 0
for i, n in enumerate(nums):
if self.hammingWeight(i) == k:
total += n
return total

Bit Length​

A close cousin of popcount: instead of counting how many bits are set, count how many bits it takes to represent the number at all - the position of the highest set bit, plus one. The same shift loop applies, just without checking the bit's value.

Find Bit Length of a Number​

Basic·
FIG. FIND BIT LENGTH OF A NUMBER● INTERACTIVE
visualization loads as you reach it
def bitsLength(n):
count = 0
while n:
n >>= 1
count += 1
return count

Hamming Distance​

Counting the positions where two numbers differ is popcount with one extra step: XOR them first, so every differing position becomes a 1, then count. The same shape covers "how many flips to turn a into b" and its multi-operand variants.

461. Hamming Distance​

Easy·
FIG. 461 HAMMING DISTANCE● INTERACTIVE
visualization loads as you reach it
class Solution:
def hammingWeight(self, n: int) -> int:
bits = 0
while n != 0:
n = n & (n - 1) # Unset the lowest set bit
bits += 1
return bits
 
def hammingDistance(self, x: int, y: int) -> int:
xor = x ^ y
return self.hammingWeight(xor)

2220. Minimum Bit Flips to Convert Number​

Easy·
FIG. 2220 MINIMUM BIT FLIPS TO CONVERT NUMBER● INTERACTIVE
visualization loads as you reach it
class Solution:
def hammingWeight(self, n: int) -> int:
bits = 0
while n != 0:
n = n & (n - 1) # Unset the lowest set bit
bits += 1
return bits
 
def minBitFlips(self, start: int, goal: int) -> int:
xor = start ^ goal
return self.hammingWeight(xor)

1318. Minimum Flips to Make a OR b Equal to c​

4 Approaches
FIG. 1318 HAMMING● INTERACTIVE
visualization loads as you reach it
class Solution:
def hammingWeight(self, n: int) -> int:
bits = 0
while n != 0:
n = n & (n - 1) # Unset the lowest set bit
bits += 1
return bits
 
def minFlips(self, a: int, b: int, c: int) -> int:
# a b a|b a&b c steps
# 0 0 |=0 &=0 0 =0
# 0 0 |=0 &=0 1 =1
# 1 0 |=1 &=0 0 =1
# 1 0 |=1 &=0 1 =0
# 1 1 |=1 &=1 0 =2 <<- (+1); can be found when AND=1 and c=0
# 1 1 |=1 &=1 1 =0 ----vvvvvvvvvvvvvvvv----
return self.hammingWeight((a | b) ^ c) + self.hammingWeight((a & b) & ((a | b) ^ c))

2997. Minimum Number of Operations to Make Array XOR Equal to K​

Medium·
FIG. 2997 MINIMUM NUMBER OF OPERATIONS TO MAKE ARRAY XOR EQUAL TO K● INTERACTIVE
visualization loads as you reach it
class Solution:
def hammingWeight(self, n: int) -> int:
bits = 0
while n != 0:
n = n & (n - 1) # Unset the lowest set bit
bits += 1
return bits
 
def minOperations(self, nums: List[int], k: int) -> int:
xor = 0
for i in nums:
xor = xor ^ i
return self.hammingWeight(xor ^ k)

Enumerate by Popcount​

Here the popcount is a filter or a key, not the answer. Walk a small search space and keep only the candidates with the right number of set bits, or exploit the parity of the popcount to answer in O(1) what a simulation would take O(2^n) to reach.

401. Binary Watch​

Easy·
2 Approaches
class Solution:
def readBinaryWatch(self, turnedOn: int) -> List[str]:
def onesCount(num):
count = 0
while num:
num = num & (num - 1)
count += 1
return count
 
ones_map = {}
for i in range(0, 60):
ones_map[i] = onesCount(i)
hashmap = collections.defaultdict(list)
 
for hour in range(0, 12):
for minute in range(0, 60):
ones = ones_map[hour] + ones_map[minute]
hashmap[ones].append(f"{hour}:{minute:02}")
 
return hashmap[turnedOn]

3304. Find the K-th Character in String Game I​

Easy·
2 Approaches
class Solution:
def kthCharacter(self, k: int) -> str:
char = "b"
word = "ab"
while len(word) < k:
new_char = []
for i in char:
new_char.append(chr(ord(i) + 1))
char += "".join(new_char)
word = word + char
return word[k - 1]