Skip to main content

Bit Patterns & Properties

These problems ask about the shape of a bit pattern: where the ones sit, how far apart they are, whether they alternate, what survives when you fold a whole range together. Counting is not enough here - position matters.

Two identities do most of the work. n & (n - 1) clears the lowest set bit, so it is zero exactly when at most one bit was set. n & -n isolates that lowest set bit, so it tells you where the pattern starts. See Core Techniques for both.

Parity Check​

The simplest bit pattern question of all: is the lowest bit set? n & 1 isolates it, answering odd-or-even in one step with no division.

Odd or Even​

Basic·
Explanation

A number is even exactly when its least significant bit is unset. n & 1 isolates that bit, so n & 1 == 0 is true only for even n.

Analysis
Time
O(1)
  • A single bitwise AND and comparison.
Space
O(1)
  • No extra space is allocated.
FIG. ODD OR EVEN● INTERACTIVE
visualization loads as you reach it
class Solution:
def isEven(self, n):
return n & 1 == 0

Powers of Two​

A power of two has exactly one set bit, so n > 0 and n & (n - 1) == 0 settles it in one step - no loop, no logarithm. A power of four adds a position constraint on top: the single bit must land on an even index, which a constant mask like 0x55555555 checks directly.

231. Power of Two​

Easy·
2 Approachesclick to switch
Explanation

A power of two has exactly one set bit in its binary representation. The trick n & (n - 1) clears the lowest set bit of n. If that single bit was the only one, the result is 0.

So n is a power of two when n > 0 and n & (n - 1) == 0.

Analysis
Time
O(1)
  • A single bitwise AND and comparison.
Space
O(1)
  • No extra space is allocated.
FIG. 231 UNSET● INTERACTIVE
visualization loads as you reach it
class Solution:
def isPowerOfTwo(self, n: int) -> bool:
return n > 0 and n & (n - 1) == 0

342. Power of Four​

Easy·
Explanation

First confirm n is a power of two: n > 0 and n & (n - 1) == 0. That guarantees a single set bit, but it could sit at an even or odd position.

A power of four is an even power of two, so its single bit lands at an even index (0, 2, 4, ...). The mask 0b10101010101010101010101010101010 has all its bits at odd positions. ANDing the number with this mask yields 0 only when the set bit is at an even position - exactly the powers of four.

Analysis
Time
O(1)
  • Three constant-time bitwise checks.
Space
O(1)
  • No extra space is allocated.
FIG. 342 POWER OF FOUR● INTERACTIVE
visualization loads as you reach it
class Solution:
def isPowerOfFour(self, n: int) -> bool:
return (
(n > 0)
and (n & (n - 1) == 0)
and (n & 0b10101010101010101010101010101010 == 0)
)

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

Easy·
Explanation

Each step is either "divide by 2" (when even) or "subtract 1" (when odd). In binary, dividing by 2 is a right shift, and subtracting 1 from an odd number clears its lowest set bit.

So while num is nonzero, every iteration costs one shift step, plus an extra subtraction step whenever the lowest bit is set (num & 1). The final right shift past the last bit overcounts by one, hence steps - 1 (and 0 for the num = 0 case).

Analysis
Time
O(log N)
  • One iteration per bit of num.
Space
O(1)
  • Only a step counter is maintained.
FIG. 1342 NUMBER OF STEPS TO REDUCE A NUMBER TO ZERO● INTERACTIVE
visualization loads as you reach it
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

Shape of the Pattern​

Now the question is about spacing and runs. Alternating bits means n ^ (n >> 1) is all ones. A binary gap means the distance between consecutive set bits. Consecutive set bits mean n & (n >> 1) is non-zero. Each of these turns a "scan the string" description into one shift-and-mask expression.

693. Binary Number with Alternating Bits​

Easy·
Explanation

If bits alternate (like 1010 or 0101), then n and n >> 1 never share a set bit at the same position - so n & (n >> 1) is 0. That alone catches the alternating pattern.

The second condition (n & (n >> 2)) == (n >> 2) confirms bits two apart are identical, ruling out edge cases and reinforcing the period-2 structure. Both must hold.

Analysis
Time
O(1)
  • A handful of constant-time shifts and comparisons.
Space
O(1)
  • No extra space is allocated.
FIG. 693 BINARY NUMBER WITH ALTERNATING BITS● INTERACTIVE
visualization loads as you reach it
class Solution:
def hasAlternatingBits(self, n: int) -> bool:
return n & (n >> 1) == 0 and (n & (n >> 2)) == (n >> 2)

868. Binary Gap​

Easy·
Explanation

The binary gap is the largest distance between two consecutive set bits. Scan n bit by bit from the least significant end, tracking the position pos and the position of the previous set bit (last_pos).

Every time the current bit is 1, if we have already seen a set bit, the distance pos - last_pos is a candidate gap. Update the running maximum and then record this position as the new last_pos.

Analysis
Time
O(1)
  • At most 32 iterations for a 32-bit integer.
Space
O(1)
  • A few scalar variables.
FIG. 868 BINARY GAP● INTERACTIVE
visualization loads as you reach it
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

3950. Exactly One Consecutive Set Bits Pair​

Easy·
2 Approachesclick to switch
Explanation

Peel off n's bits one at a time with divmod(n, 2), recording every position i where the remainder is 1 into ones. Then scan adjacent entries of ones: whenever two recorded positions are exactly 1 apart, that's one consecutive set-bits pair. Exactly one such adjacency means len(consec) == 1.

Analysis
Time
O(1)
  • A fixed 32 iterations to peel bits, plus a bounded scan over the recorded positions.
Space
O(1)
  • ones and consec hold at most 32 entries each.
FIG. 3950 POSITIONS● INTERACTIVE
visualization loads as you reach it
class Solution:
def consecutiveSetBits(self, n: int) -> bool:
ones = []
for i in range(32):
n, rem = divmod(n, 2)
if rem:
ones.append(i)
consec = []
for i in range(1, len(ones)):
if ones[i] == ones[i - 1] + 1:
consec.append(i - 1)
return len(consec) == 1

2980. Check if Bitwise OR Has Trailing Zeros​

Easy·
Explanation

The bitwise OR of a subset has a trailing zero (its lowest bit is 0) only if every number in that subset has its lowest bit 0 - that is, every number is even. So the question reduces to: are there at least two even numbers we can OR together?

Walk the array counting evens (i & 1 == 0). The moment the count reaches 2, return True.

Analysis
Time
O(n)
  • n is the length of nums - the for i in nums loop makes one pass, stopping early once two evens are found.
Space
O(1)
  • Only the evens counter is kept, regardless of array length.
FIG. 2980 CHECK IF BITWISE OR HAS TRAILING ZEROS● INTERACTIVE
visualization loads as you reach it
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

1016. Binary String With Substrings Representing 1 To N​

Medium·
Explanation

The binary of i is the binary of 2 * i (or 2 * i + 1) with its last bit dropped - bin(2 * i)[2:] == bin(i)[2:] + "0". So if every number in the upper half (n // 2, n] is present as a substring, every smaller number is automatically present as a prefix of one of them.

That halves the work to one loop counting down from n to n // 2 + 1, testing bin(i)[2:] not in s with Python's substring search. The first miss returns False.

Analysis
Time
O(N · |s|)
  • N / 2 iterations, each running a substring search over s that costs O(|s|).
Space
O(log N)
  • Only the binary string of i, which is O(log N) characters wide.
FIG. 1016 BINARY STRING WITH SUBSTRINGS REPRESENTING 1 TO N● INTERACTIVE
visualization loads as you reach it
class Solution:
def queryString(self, s: str, n: int) -> bool:
for i in range(n, n // 2, -1):
if bin(i)[2:] not in s:
return False
return True

Across a Range​

Folding an operator over every value in [left, right] looks like an O(n) loop but is not. AND across a range keeps only the common binary prefix of the endpoints, because somewhere in the range every lower bit flips to zero. OR across a set behaves the opposite way: it saturates fast, so the first value it cannot produce is small.

201. Bitwise AND of Numbers Range​

Medium·
5 Approachesclick to switch
Explanation

ANDing every number in [left, right] zeroes out any bit position that flips somewhere in the range. Only the common high-order prefix of left and right survives.

Right-shift both endpoints until they become equal, counting the shifts. At that point the shared bits line up in right; shift it back left by the same count to restore the trailing zeros.

Analysis
Time
O(log N)
  • One shift per differing bit.
Space
O(1)
  • Only a shift counter is tracked.
FIG. 201 SHIFT● INTERACTIVE
visualization loads as you reach it
class Solution:
def rangeBitwiseAnd(self, left: int, right: int) -> int:
shift = 0
while left < right:
left >>= 1
right >>= 1
shift += 1
return right << shift

2568. Minimum Impossible OR​

Medium·
Explanation

Any value that is not a power of two can be built by ORing the powers of two present in its binary representation. So the only values that can be "impossible" are powers of two themselves - and a power of two 2^k is expressible only if 2^k is literally in the array (ORing other elements can never produce a lone power-of-two value not already present).

Therefore the answer is the smallest power of two missing from the array. Start at 1 and keep doubling while the current power is in the set.

Analysis
Time
O(N + log M)
  • Building the set is O(N); the loop runs once per power of two up to the max value M.
Space
O(N)
  • The set stores the array elements.
FIG. 2568 MINIMUM IMPOSSIBLE OR● INTERACTIVE
visualization loads as you reach it
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