Bit Masks: Set, Clear, Toggle, Check
Implement helpers to set, clear, toggle, and check individual bits, and apply bit masks to represent subsets in subset-enumeration problems.
What Are Bit Masks?
A bit mask is an integer used to select, modify, or test specific bits in another integer. The mask has 1s in the positions you care about and 0s elsewhere. Combined with bitwise operators, masks let you perform fine-grained bit operations without affecting other bits.
The four fundamental mask operations are: set (turn a bit on), clear (turn a bit off), toggle (flip a bit), and check (test whether a bit is 1). Each uses a different operator — OR, AND-NOT, XOR, and AND respectively — with the mask 1 << k.
# The four fundamental bit mask operations
def set_bit(n, k): return n | (1 << k) # OR to set
def clear_bit(n, k): return n & ~(1 << k) # AND-NOT to clear
def toggle_bit(n, k): return n ^ (1 << k) # XOR to toggle
def check_bit(n, k): return (n >> k) & 1 # shift+AND to check
n = 0b10110101 # 181
print(f'n = {bin(n)}')
print(f'set bit 1: {bin(set_bit(n, 1))}')
print(f'clear bit 2: {bin(clear_bit(n, 2))}')
print(f'toggle bit 0: {bin(toggle_bit(n, 0))}')
print(f'check bit 4: {check_bit(n, 4)}')Set Bit: Turning a Bit On
To set bit k (force it to 1 regardless of its current value), OR the number with the mask 1 << k. Since 0 OR 1 = 1 and 1 OR 1 = 1, the target bit becomes 1. All other bits are OR'd with 0, which leaves them unchanged.
Setting a bit is idempotent — calling it multiple times has the same effect as calling it once. If bit k is already 1, the result is unchanged. This property is important for flag management where you want to enable a feature without worrying about its current state.
def set_bit(n, k):
mask = 1 << k
return n | mask
# Set various bits
n = 0b00001010 # 10
print(f'Original: {bin(n)} = {n}')
for k in [0, 3, 6, 7]:
result = set_bit(n, k)
print(f'Set bit {k}: {bin(result)} = {result}')
# Idempotence: setting already-set bit does nothing
n = 0b1111
print(f'\nAlready set: {bin(set_bit(n, 2))} = {bin(n)} (unchanged)')
# Setting multiple bits at once with a combined mask
mask = (1 << 0) | (1 << 2) | (1 << 4) # bits 0, 2, 4
print(f'Set bits 0,2,4: {bin(0 | mask)} = {0 | mask}')All lessons in this course
- Bitwise Operators: AND, OR, XOR, NOT, Shifts
- Single Number and XOR Properties
- Bit Masks: Set, Clear, Toggle, Check
- Counting Bits, Missing Number, and Reverse Bits