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·
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 Approaches
class Solution:
def isPowerOfTwo(self, n: int) -> bool:
return n > 0 and n & (n - 1) == 0

342. Power of Four​

Easy·
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·
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·
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·
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 Approaches
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·
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·
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 Approaches
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·
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