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 Approachesclick to switch
Explanation

The number of set bits is the Hamming weight. Test the least significant bit with n & 1, add it to the count, then right-shift n to expose the next bit. The loop ends once n becomes 0. This visits every bit position, set or not.

Analysis
Time
O(1)
  • Bounded by the fixed 32-bit width of n.
Space
O(1)
  • Only the counter is stored.
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 Approachesclick to switch
Explanation

Brian Kernighan's trick clears the lowest set bit: i & (i - 1). That gives a recurrence, popcount(i) = 1 + popcount(i & (i - 1)), with base case popcount(0) = 0. Write it as a bare top-down recursion and let @lru_cache memoize every call. The one thing to watch: the answer is the whole array of counts for 0..n, not just popcount(n), so the recursion is called once per index and collected into a list.

Analysis
Time
O(n)
  • @lru_cache means each of the n distinct subproblems is solved once; every other call is a cache hit.
Space
O(n)
  • The cache holds up to n entries, plus the n + 1-element result list.
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·
Explanation

Walk the bits from least significant upward, tracking the position pos. Whenever the LSB is set, increment even if pos is even and odd if pos is odd. Shift right to advance and stop once n is 0.

Analysis
Time
O(log N)
  • One iteration per bit of n.
Space
O(1)
  • Two counters and a position index.
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·
Explanation

Sort with a composite key: first by number of set bits, then by the value itself to break ties. Python's sorted is stable, so the (hammingWeight(i), i) tuple orders elements with the same bit count by their natural value.

Analysis
Time
O(N log N)
  • sorted makes O(N log N) comparisons, and each of the N elements computes its (hammingWeight(i), i) key once.
Space
O(sort + N)
  • sorted returns a new list of N elements, on top of the sort's own working memory.
  • Sorting algorithms are typically O(log n) space (in-place, recursion stack only), but Python's sorted() is Timsort, which allocates up to O(n) auxiliary space in the worst case - that's what sort stands for here.
FIG. 1356 SORT INTEGERS BY THE NUMBER OF 1 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 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·
Explanation

Scan each element with its index. The condition is about the index, not the value: count the set bits of i, and if that equals k, add nums[i] to the running total.

Analysis
Time
O(N log N)
  • Each of the N indices needs a Hamming-weight count over its bits.
Space
O(1)
  • Only the running total is stored.
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·
Explanation

The bit length is the position of the highest set bit, plus one. Right-shifting n one bit at a time discards the lowest bit each time; counting shifts until n becomes 0 counts exactly that many bit positions - equivalent to Python's built-in n.bit_length().

Analysis
Time
O(log n)
  • The while n loop shifts n right by one bit each iteration until it reaches 0, once per bit of n: O(log n).
Space
O(1)
  • Only the counter is maintained.
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·
Explanation

The Hamming distance is the number of bit positions where x and y differ. XOR outputs 1 exactly where two bits disagree, so x ^ y marks every differing position. Counting the set bits of that XOR gives the distance directly.

Analysis
Time
O(1)
  • Bounded by the fixed bit width of the integers.
Space
O(1)
  • Only the XOR and counter are stored.
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·
Explanation

Converting start to goal one bit at a time costs one flip per differing bit - which is exactly the Hamming distance. XOR the two numbers to mark every position that differs, then count the set bits of the result.

Analysis
Time
O(1)
  • Bounded by the fixed bit width of the integers.
Space
O(1)
  • Only the XOR and counter are stored.
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 Approachesclick to switch
Explanation

We need a | b == c. Wherever (a | b) ^ c is 1 the bits disagree and must be flipped, so counting those set bits gives the base answer. One exception: when c's bit is 0 but both a and b have a 1 there, a single flip is not enough - both must be cleared, costing an extra flip. Those positions are exactly where a & b is set and the mismatch is set, so add their count too.

Analysis
Time
O(2 log N)
  • Two separate hammingWeight calls, each a Kernighan's-algorithm loop bounded by the bit width - log N + log N collapses to 2 log N.
Space
O(1)
  • No additional space beyond the bits counter inside each hammingWeight call.
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·
Explanation

Each operation flips a single bit of one element, which flips that bit in the overall XOR. So the task reduces to the Hamming distance: fold the array into a running XOR, then count the set bits of xor ^ k - that is how many bit positions must change to turn the current XOR into k.

Analysis
Time
O(n)
  • n = len(nums). The for i in nums loop folds every element into xor once - O(n) - then hammingWeight strips one bit at a time from a fixed-width integer, a constant number of iterations independent of n.
Space
O(1)
  • Only the xor and bits accumulators are stored; nothing scales with n.
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 Approachesclick to switch
Explanation

Only 720 valid times exist, so enumerate them all instead of choosing which LEDs to light. Precompute the Hamming weight of every value 0..59 with num & (num - 1), then bucket each hour:minute pair under ones_map[hour] + ones_map[minute]. The answer for any turnedOn is a dictionary lookup.

Analysis
Time
O(1)
  • 60 popcounts plus a fixed 12 x 60 sweep - the work never depends on the input.
Space
O(1)
  • The popcount table and the bucket map hold a fixed 60 + 720 entries.
FIG. 401 BINARY WATCH TABLE● INTERACTIVE
visualization loads as you reach it
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 Approachesclick to switch
Explanation

Play the game literally: word starts as "ab". Each round, a new block is produced by shifting every character of the block just added one letter forward (chr(ord(i)+1)), and that new block is appended to both char (the running "delta" block) and word. Repeat until word is at least k characters long, then read off index k - 1.

Analysis
Time
O(k)
  • word roughly doubles in length each round, so the total work across all rounds sums to O(k).
Space
O(k)
  • word and char grow to O(k) characters before the loop stops.
FIG. 3304 FIND THE K TH CHARACTER IN STRING GAME I● INTERACTIVE
visualization loads as you reach it
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]