Skip to main content

Bit Manipulation

These are the foundational techniques - the building blocks almost every problem in this section reuses. Trace each one until the binary cells feel natural, then work through the problem pages: Single-Integer Bits (complement, counting set bits, powers and properties) and XOR & Bitmask Sets (XOR tricks, single number, sets as bitmasks, in-place index marking).

Bit Manipulation
Foundational Tricks
Single Bit
inspect or isolate one bit
LSB Check
n & 1 -- odd or even
Isolate LSB
x & -x -- rightmost set bit
Clearing Bits
turn bits off
Brian Kernighan
n & (n - 1) -- drop lowest set bit
Whole Number
transform all bits
Negate Bits
XOR with all-ones mask
Reverse Bits
mask-and-shift halving
No Extra Space
in-place identities
XOR Swap
swap without a temp
+
−
⟲
⛶

Negating Bits in a Number​

Negating Bits in a Number

Solutions:
FIG. FOUNDATIONS NEGATE BITS● INTERACTIVE
Visualize
def negate_bits(num: int) -> int:
bit_length = num.bit_length()
bitmask = (1 << bit_length) - 1 # binary with all 1's
return num ^ bitmask

Checking the Least Significant Bit (Odd / Even)​

Checking the Least Significant Bit (Odd / Even)

Solutions:
FIG. FOUNDATIONS LSB CHECK● INTERACTIVE
Visualize
def check_least_significant_bit(n: int) -> bool:
return n & 1 == 1

Unsetting the Lowest Set Bit, Brian Kernighan's Algorithm​

Unsetting the Lowest Set Bit, Brian Kernighan's Algorithm

Solutions:
FIG. FOUNDATIONS UNSET LSB● INTERACTIVE
Visualize
def unset_least_significant_bit(n: int) -> int:
return n & (n - 1)

Isolating the Lowest Set Bit​

Isolating the Lowest Set Bit

Solutions:
FIG. FOUNDATIONS ISOLATE LSB● INTERACTIVE
Visualize
def isolate_least_significant_set_bit(x: int) -> int:
return x & -x

Reversing the Bits of a 32-bit Integer​

Reversing the Bits of a 32-bit Integer

Solutions:
FIG. FOUNDATIONS REVERSE BITS● INTERACTIVE
Visualize
class Solution:
def reverseBits(self, n):
n = ((n & 0b11111111111111111111111111111111) >> 16) | (
(n & 0b11111111111111111111111111111111) << 16
)
n = ((n & 0b11111111000000001111111100000000) >> 8) | (
(n & 0b00000000111111110000000011111111) << 8
)
n = ((n & 0b11110000111100001111000011110000) >> 4) | (
(n & 0b00001111000011110000111100001111) << 4
)
n = ((n & 0b11001100110011001100110011001100) >> 2) | (
(n & 0b00110011001100110011001100110011) << 2
)
n = ((n & 0b10101010101010101010101010101010) >> 1) | (
(n & 0b01010101010101010101010101010101) << 1
)
return n

Swapping Two Variables Without a Temp​

Swapping Two Variables Without a Temp

Solutions:
FIG. FOUNDATIONS XOR SWAP● INTERACTIVE
Visualize
def swap_nums(a, b):
a = a ^ b
b = b ^ a
a = a ^ b
return a, b