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.

Single-Integer Bits
operate on one number's bits
Complement
flip every bit within the width
All-ones mask
n ^ mask
Bit by bit
rebuild inverted
Counting Bits
how many 1s, and where
Hamming weight
n & (n - 1)
Hamming distance
XOR then count
Reverse bits
mask and shift
Powers & Properties
structural tests on the bits
One set bit
n & (n - 1) == 0
Scan the bits
gap / steps / alternating
Range AND
common prefix
+
−
⟲
⛶

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·
476. Number Complement
flip every used bit
All-Ones Mask
grow a mask, XOR once
findComplement
mask of 1s as wide as n, then n ^ mask
Bit by Bit
rebuild from each flipped bit
bitwiseComplement
read each bit, append its inverse
+
−
⟲
⛶
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·
191. Number of 1 Bits
count set bits (Hamming weight)
Check Each Bit
test the LSB, then shift
n & 1
loops once per bit position
Drop Set Bits
strip one 1 per step
n & (n - 1)
loops once per set bit only
+
−
⟲
⛶
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·
1318. Min Flips a OR b == c
make a | b equal c
Hamming Weight
count mismatched bits in one shot
(a | b) ^ c
set bits = positions to fix
(a & b) & mismatch
the +1 case when c-bit is 0
Bit by Bit
decide per position
c-bit set
need at least one of a, b set
c-bit clear
flip every set bit of a and b
+
−
⟲
⛶
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·
190. Reverse Bits
mirror all 32 bits
Bit by Bit
pour LSBs into a growing result
32 iterations
shift result left, append n & 1
Mask and Shift
swap halves, recurse on blocks
5 fixed ops
16, 8, 4, 2, 1-bit block swaps
+
−
⟲
⛶
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 & Properties​

These test or exploit a number's structural bit properties: powers of two/four have exactly one set bit (n & (n - 1) == 0); other problems scan the bits LSB-to-MSB or reason about how bits behave across a whole range of values.

231. Power of Two​

Easy·
Power of Two
exactly one set bit
Unset LS 1-Bit
n & (n - 1) clears lowest set bit
result is 0
the only set bit was the lowest
Isolate LS 1-Bit
n & (-n) keeps only lowest set bit
equals n
the isolated bit is the whole number
+
−
⟲
⛶
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·
Bitwise AND of Range
keep the common prefix
Common Prefix by Shifting
drop differing low bits
shift both until equal
count shifts, then shift back
Unset Bits in right
Brian Kernighan
clear low set bits of right
until right <= left
+
−
⟲
⛶
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:]