Skip to main content

Single-Integer Bits

Every problem here works on a single integer's bits - flipping them, counting them, or testing their structure. The recurring identities are n & (n - 1) (clear the lowest set bit) and n & -n (isolate it); see Bit Manipulation for the building blocks.

Complement​

Flipping every bit of a number within its own width is the negate-bits trick - XOR with an all-ones mask, or rebuild the number bit by bit.

476. Number Complement​

Easy·
Solutions:
Visualize
class Solution:
def findComplement(self, num: int) -> int:
bitmask = 1
while bitmask < num:
bitmask = bitmask << 1 | 1
return num ^ bitmask

1009. Complement of Base 10 Integer​

Easy·
Solutions:
Visualize
class Solution:
def bitwiseComplement(self, n: int) -> int:
bitmask = 1
while bitmask < n:
bitmask = bitmask << 1 | 1
return n ^ bitmask

Counting Set Bits​

Almost every problem here reduces to the same primitive - count the set bits of an integer. Hamming weight counts the 1s in one number; Hamming distance XORs two numbers first; reversing mirrors the bit order; and the array problems use a set-bit count as a key or filter.

191. Number of 1 Bits​

Easy·
Solutions:
Visualize
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

2595. Number of Even and Odd Bits​

Easy·
Solutions:
Visualize
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]

461. Hamming Distance​

Easy·
Solutions:
Visualize
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·
Solutions:
Visualize
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​

Medium·
Solutions:
Visualize
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)
)

190. Reverse Bits​

Easy·
Solutions:
Visualize
class Solution:
def reverseBits(self, n: int) -> int:
r = 0
for i in range(32):
r = (r << 1) | (n & 1)
n >>= 1
return r

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

Easy·
Solutions:
Visualize
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

1356. Sort Integers by The Number of 1 Bits​

Easy·
Solutions:
Visualize
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))

2657. Find the Prefix Common Array of Two Arrays​

Medium·
Solutions:
Visualize
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 findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:
bitmap_a = bitmap_b = 0
ans = []
for i in range(len(A)):
bitmap_a = bitmap_a | (1 << A[i])
bitmap_b = bitmap_b | (1 << B[i])
ans.append(self.hammingWeight(bitmap_a & bitmap_b))
return ans

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

Medium·
Solutions:
Visualize
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)

Powers and Properties​

These problems test or exploit a number's structural bit properties: how many bits are set, where they sit, and how bits behave across a range of values. A power of two has exactly one set bit, so n & (n - 1) == 0 settles it in one step.

231. Power of Two​

Easy·
Solutions:
Visualize
class Solution:
def isPowerOfTwo(self, n: int) -> bool:
return n > 0 and n & (n - 1) == 0

342. Power of Four​

Easy·
Solutions:
Visualize
class Solution:
def isPowerOfFour(self, n: int) -> bool:
return (
(n > 0)
and (n & (n - 1) == 0)
and (n & 0b10101010101010101010101010101010 == 0)
)

2980. Check if Bitwise OR Has Trailing Zeros​

Easy·
Solutions:
Visualize
class Solution:
def hasTrailingZeros(self, nums: List[int]) -> bool:
evens = 0
for i in nums:
if i & 1 == 0:
evens += 1
if evens >= 2:
return True
return False

868. Binary Gap​

Easy·
Solutions:
Visualize
class Solution:
def binaryGap(self, n: int) -> int:
last_pos = None
pos = 0
maxi = 0
while n:
if n & 1:
if last_pos is not None:
maxi = max(maxi, pos - last_pos)
last_pos = pos
n = n >> 1
pos += 1
return maxi

1342. Number of Steps to Reduce a Number to Zero​

Easy·
Solutions:
Visualize
class Solution:
def numberOfSteps(self, num: int) -> int:
steps = 0
while num:
if num & 1:
steps += 1
steps += 1
num = num >> 1
return steps - 1 if steps else 0

693. Binary Number with Alternating Bits​

Easy·
Solutions:
Visualize
class Solution:
def hasAlternatingBits(self, n: int) -> bool:
return n & (n >> 1) == 0 and (n & (n >> 2)) == (n >> 2)

201. Bitwise AND of Numbers Range​

Medium·
Solutions:
Visualize
class Solution:
def rangeBitwiseAnd(self, left: int, right: int) -> int:
shifts = 0
while left != right:
left >>= 1
right >>= 1
shifts += 1
return left << shifts

2568. Minimum Impossible OR​

Medium·
Solutions:
Visualize
class Solution:
def minImpossibleOR(self, nums: List[int]) -> int:
nums_set = set(nums)
look_for = 1
while look_for in nums_set:
look_for <<= 1
return look_for

1256. Encode Number​

Medium·
Solutions:
Visualize
class Solution:
def encode(self, num: int) -> str:
return bin(num + 1)[3:]