Loading learning content...
In the previous page, we learned to read bits at any position—checking whether they're set and extracting their values. Now we complete the toolkit by learning to write bits: setting them to 1, clearing them to 0, or toggling their current state.
These three operations—set, clear, and toggle—give you complete control over individual bits. Combined with the reading techniques from the previous page, you can implement any bit manipulation pattern.
This page covers not just the mechanics, but also practical applications like state machines, feature flags, and efficient data manipulation—skills you'll use throughout your programming career.
By the end of this page, you will master setting bits to 1 using OR, clearing bits to 0 using AND with inverted mask, toggling bits using XOR, combining operations for complex manipulations, and practical applications in state management and data encoding.
To set bit k to 1 (regardless of its current value), we use the OR operator with a positional mask:
$$n = n \mid (1 << k)$$
Why OR works:
Recall the OR truth table:
0 OR 0 = 0
0 OR 1 = 1
1 OR 0 = 1
1 OR 1 = 1
OR with 1 always produces 1. OR with 0 preserves the original value.
When we OR with 1 << k:
Example: Set bit 2 in n = 9 (1001₂)
n = 1001 (9)
1 << 2 = 0100 (4)
n | mask = 1101 (13) ← bit 2 is now set
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566
def set_bit(n: int, k: int) -> int: """ Set bit at position k to 1. Args: n: The number to modify k: The bit position to set (0-indexed from right) Returns: The number with bit k set to 1 Time: O(1) Space: O(1) Examples: set_bit(9, 2) # 9 = 1001 → 1101 = 13 set_bit(9, 0) # 9 = 1001 → 1001 = 9 (already set) set_bit(0, 3) # 0 = 0000 → 1000 = 8 """ return n | (1 << k) def set_multiple_bits(n: int, positions: list[int]) -> int: """Set multiple bits at once.""" mask = 0 for k in positions: mask |= (1 << k) return n | mask def set_bit_visual(n: int, k: int, width: int = 8) -> int: """Set bit with visualization.""" mask = 1 << k result = n | mask fmt = lambda x: format(x & ((1 << width) - 1), f'0{width}b') print(f"Set bit {k} in {n}:") print(f" n = {fmt(n)} ({n})") print(f" mask = {fmt(mask)} (1 << {k})") print(f" result = {fmt(result)} ({result})") print() return result # Demonstrationprint("=== Setting Bits ===") # Basic examplesset_bit_visual(9, 2) # 1001 → 1101set_bit_visual(0, 5) # Set bit in zeroset_bit_visual(9, 0) # Already set - no change # Set multiple bitsprint("Set multiple bits (0, 2, 4) in 0:")result = set_multiple_bits(0, [0, 2, 4])print(f" Result: {format(result, '08b')} ({result})")print() # Build a number bit by bitprint("Building the number 42 (101010) bit by bit:")n = 0for pos, desc in [(1, "Set bit 1"), (3, "Set bit 3"), (5, "Set bit 5")]: n = set_bit(n, pos) print(f" {desc}: n = {format(n, '08b')} ({n})")To clear bit k (set it to 0, regardless of its current value), we use AND with an inverted mask:
$$n = n & \sim(1 << k)$$
Why AND with inverted mask works:
The mask ~(1 << k) has 0 only at position k, and 1s everywhere else:
1 << 2 = 00000100
~(1 << 2)= 11111011 ← 0 only at position 2
Recall the AND truth table:
1 AND 1 = 1
1 AND 0 = 0
0 AND 1 = 0
0 AND 0 = 0
AND with 0 always produces 0. AND with 1 preserves the original value.
When we AND with ~(1 << k):
Example: Clear bit 3 in n = 15 (1111₂)
n = 1111 (15)
~(1 << 3) = 0111 (inverted mask, only showing 4 bits)
n & ~(1 << 3) = 0111 (7) ← bit 3 is now cleared
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374
def clear_bit(n: int, k: int) -> int: """ Clear bit at position k (set to 0). Args: n: The number to modify k: The bit position to clear (0-indexed from right) Returns: The number with bit k set to 0 Time: O(1) Space: O(1) Examples: clear_bit(15, 3) # 15 = 1111 → 0111 = 7 clear_bit(15, 0) # 15 = 1111 → 1110 = 14 clear_bit(8, 3) # 8 = 1000 → 0000 = 0 """ return n & ~(1 << k) def clear_multiple_bits(n: int, positions: list[int]) -> int: """Clear multiple bits at once.""" mask = 0 for k in positions: mask |= (1 << k) return n & ~mask # AND with inverted combined mask def clear_bit_visual(n: int, k: int, width: int = 8) -> int: """Clear bit with visualization.""" mask = 1 << k inv_mask = ~mask result = n & inv_mask # For display, mask to width bits def fmt(x): return format(x & ((1 << width) - 1), f'0{width}b') print(f"Clear bit {k} in {n}:") print(f" n = {fmt(n)} ({n})") print(f" 1 << {k} = {fmt(mask)}") print(f" ~(1 << {k}) = {fmt(inv_mask)} (inverted mask)") print(f" result = {fmt(result)} ({result})") print() return result # Demonstrationprint("=== Clearing Bits ===") # Basic examplesclear_bit_visual(15, 3) # 1111 → 0111clear_bit_visual(15, 0) # 1111 → 1110clear_bit_visual(8, 3) # 1000 → 0000 (single bit cleared to zero) # Clear multiple bitsprint("Clear multiple bits (1, 2, 3) in 255:")result = clear_multiple_bits(255, [1, 2, 3])print(f" 255 = {format(255, '08b')}")print(f" Result: {format(result, '08b')} ({result})")print() # Common pattern: Clear lower k bitsdef clear_lower_bits(n: int, k: int) -> int: """Clear the lowest k bits (bits 0 through k-1).""" mask = (1 << k) - 1 # Mask with k lowest bits set return n & ~mask print("Clear lowest 3 bits of 255:")result = clear_lower_bits(255, 3)print(f" 255 = {format(255, '08b')} → {format(result, '08b')} ({result})")Set uses OR (to add a 1). Clear uses AND with NOT (to force a 0). Think of it as: OR adds the bit, AND with inverted mask removes the bit.
To toggle bit k (flip 0 to 1 or 1 to 0), we use XOR with the positional mask:
$$n = n \oplus (1 << k)$$
Why XOR works:
Recall the XOR truth table:
0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0
XOR with 1 flips the bit. XOR with 0 preserves the bit.
When we XOR with 1 << k:
Example: Toggle bit 2 in n = 5 (0101₂)
n = 0101 (5)
1 << 2 = 0100 (4)
n ^ mask = 0001 (1) ← bit 2 toggled from 1 to 0
Apply again:
0001 ^ 0100 = 0101 (5) ← back to original
Key Property: Toggling twice returns to the original value. This is the foundation of XOR-based encryption and many clever algorithms.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081
def toggle_bit(n: int, k: int) -> int: """ Toggle bit at position k (flip 0↔1). Args: n: The number to modify k: The bit position to toggle (0-indexed from right) Returns: The number with bit k flipped Time: O(1) Space: O(1) Examples: toggle_bit(5, 2) # 5 = 0101 → 0001 = 1 (1→0) toggle_bit(5, 1) # 5 = 0101 → 0111 = 7 (0→1) """ return n ^ (1 << k) def toggle_multiple_bits(n: int, positions: list[int]) -> int: """Toggle multiple bits at once.""" mask = 0 for k in positions: mask |= (1 << k) return n ^ mask def toggle_bit_visual(n: int, k: int, width: int = 8) -> int: """Toggle bit with visualization.""" mask = 1 << k result = n ^ mask fmt = lambda x: format(x & ((1 << width) - 1), f'0{width}b') original_bit = (n >> k) & 1 new_bit = (result >> k) & 1 print(f"Toggle bit {k} in {n}:") print(f" n = {fmt(n)} ({n})") print(f" mask = {fmt(mask)} (1 << {k})") print(f" result = {fmt(result)} ({result})") print(f" Bit {k}: {original_bit} → {new_bit}") print() return result # Demonstrationprint("=== Toggling Bits ===") # Basic examplestoggle_bit_visual(5, 2) # 0101 → 0001 (bit 2: 1→0)toggle_bit_visual(5, 1) # 0101 → 0111 (bit 1: 0→1) # Demonstrate toggle-twice propertyprint("Toggle twice returns to original:")n = 42print(f" Original: {n} = {format(n, '08b')}")n = toggle_bit(n, 3)print(f" Toggle 3: {n} = {format(n, '08b')}")n = toggle_bit(n, 3)print(f" Toggle 3: {n} = {format(n, '08b')} (back to original)")print() # Toggle multiple bitsprint("Toggle bits 0, 2, 4 in 0:")result = toggle_multiple_bits(0, [0, 2, 4])print(f" Result: {format(result, '08b')} ({result})")print() # Invert all bits using XOR with all-onesdef invert_bits(n: int, width: int = 8) -> int: """Invert all bits (same as ~n for fixed width).""" all_ones = (1 << width) - 1 return n ^ all_ones print("Invert all bits (8-bit):")for n in [0, 1, 15, 255, 170]: inverted = invert_bits(n) print(f" {n:3} ({format(n, '08b')}) → {inverted:3} ({format(inverted, '08b')})")Real-world bit manipulation often combines these basic operations. Let's explore common composite patterns:
| Operation | Expression | Description |
|---|---|---|
| Check bit k | (n >> k) & 1 or (n & (1<<k)) != 0 | Returns 0 or 1 / true-false |
| Set bit k | n | (1 << k) | Force bit k to 1 |
| Clear bit k | n & ~(1 << k) | Force bit k to 0 |
| Toggle bit k | n ^ (1 << k) | Flip bit k |
| Update bit k to v | (n & ~(1<<k)) | (v<<k) | Set bit k to value v (0 or 1) |
| Extract last k bits | n & ((1 << k) - 1) | Get rightmost k bits |
| Clear last k bits | n & ~((1 << k) - 1) | Zero out rightmost k bits |
| Set last k bits | n | ((1 << k) - 1) | Set rightmost k bits to 1 |
| Toggle last k bits | n ^ ((1 << k) - 1) | Flip rightmost k bits |
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586
# Advanced bit manipulation patterns def update_bit(n: int, k: int, v: int) -> int: """ Update bit at position k to value v (where v is 0 or 1). Strategy: Clear the bit first, then set it to v. """ # Clear bit k cleared = n & ~(1 << k) # Set bit k to v (v is 0 or 1) return cleared | (v << k) def modify_bits_in_range(n: int, start: int, width: int, value: int) -> int: """ Replace a range of bits [start, start+width) with a new value. Example: modify_bits_in_range(0xFF, 2, 4, 0b0101) Replaces bits 2-5 with 0101 """ # Create mask for the range mask = ((1 << width) - 1) << start # Clear the range cleared = n & ~mask # Insert new value (masked to ensure it fits) return cleared | ((value & ((1 << width) - 1)) << start) def swap_bits(n: int, i: int, j: int) -> int: """ Swap bits at positions i and j. Only swap if they're different (if same, XOR does nothing). """ # Check if bits are different bit_i = (n >> i) & 1 bit_j = (n >> j) & 1 if bit_i != bit_j: # Toggle both bits n ^= (1 << i) | (1 << j) return n def reverse_bits(n: int, width: int = 8) -> int: """ Reverse the bit order within the given width. Example: 0b10110000 (8-bit) → 0b00001101 """ result = 0 for i in range(width): if (n >> i) & 1: result |= 1 << (width - 1 - i) return result # Demonstrationsprint("=== Combined Bit Operations ===") # Update bitprint("Update bit 2 in 0b1111 to 0:")result = update_bit(0b1111, 2, 0)print(f" 1111 → {format(result, '04b')} ({result})")print() # Modify rangeprint("Modify bits 2-5 in 0xFF to 0b0101:")result = modify_bits_in_range(0xFF, 2, 4, 0b0101)print(f" Original: {format(0xFF, '08b')}")print(f" Result: {format(result, '08b')} ({result})")print() # Swap bitsprint("Swap bits 1 and 6 in 0b01000010:")n = 0b01000010result = swap_bits(n, 1, 6)print(f" {format(n, '08b')} → {format(result, '08b')}")print() # Reverse bitsprint("Reverse bits (8-bit):")for n in [0b10110000, 0b11110001, 0b10101010]: rev = reverse_bits(n, 8) print(f" {format(n, '08b')} → {format(rev, '08b')}")A powerful application of bit manipulation is implementing state machines where multiple independent boolean states are tracked efficiently. This pattern is common in game development, network protocols, and UI state management.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102
from enum import IntFlag, auto class PlayerState(IntFlag): """Player states represented as bit flags.""" IDLE = 0 # No flags set MOVING = auto() # 1 << 0 = 1 JUMPING = auto() # 1 << 1 = 2 ATTACKING = auto() # 1 << 2 = 4 DEFENDING = auto() # 1 << 3 = 8 INVULNERABLE = auto() # 1 << 4 = 16 POISONED = auto() # 1 << 5 = 32 SLOWED = auto() # 1 << 6 = 64 BUFFED = auto() # 1 << 7 = 128 class Player: """Player with bit-flag based state management.""" def __init__(self, name: str): self.name = name self._state = PlayerState.IDLE @property def state(self) -> int: return self._state def add_state(self, state: PlayerState) -> None: """Add a state flag (set bit).""" self._state |= state def remove_state(self, state: PlayerState) -> None: """Remove a state flag (clear bit).""" self._state &= ~state def toggle_state(self, state: PlayerState) -> None: """Toggle a state flag.""" self._state ^= state def has_state(self, state: PlayerState) -> bool: """Check if player has a specific state.""" return (self._state & state) == state def has_any_state(self, states: PlayerState) -> bool: """Check if player has any of the given states.""" return (self._state & states) != 0 def clear_all_states(self) -> None: """Reset to idle.""" self._state = PlayerState.IDLE def get_active_states(self) -> list: """Get list of active state names.""" return [s.name for s in PlayerState if s != 0 and self.has_state(s)] def __str__(self) -> str: states = self.get_active_states() state_str = ', '.join(states) if states else 'IDLE' return f"{self.name}: [{state_str}] (flags: {format(self._state, '08b')})" # Demonstrationprint("=== State Machine with Bit Flags ===") player = Player("Hero")print(f"Initial: {player}") # Add statesplayer.add_state(PlayerState.MOVING)print(f"After moving: {player}") player.add_state(PlayerState.JUMPING)print(f"After jump: {player}") player.add_state(PlayerState.ATTACKING)print(f"After attack: {player}") # Check statesprint(f"Is moving? {player.has_state(PlayerState.MOVING)}")print(f"Is defending? {player.has_state(PlayerState.DEFENDING)}")print(f"Is moving OR attacking? {player.has_any_state(PlayerState.MOVING | PlayerState.ATTACKING)}") # Remove stateplayer.remove_state(PlayerState.MOVING)print(f"After stop moving: {player}") # Toggle invulnerabilityplayer.toggle_state(PlayerState.INVULNERABLE)print(f"Toggle invulnerable: {player}")player.toggle_state(PlayerState.INVULNERABLE)print(f"Toggle again: {player}") # Apply debuffsplayer.add_state(PlayerState.POISONED | PlayerState.SLOWED)print(f"After debuffs: {player}") # Clear allplayer.clear_all_states()print(f"After clear: {player}")Another common application is feature flags—enabling or disabling features at runtime without code changes. This is used extensively in production systems for A/B testing, gradual rollouts, and feature management.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115
class FeatureFlags: """Feature flag management using bit manipulation.""" # Define features as bit positions DARK_MODE = 0 NOTIFICATIONS = 1 BETA_FEATURES = 2 ANALYTICS = 3 PREMIUM = 4 ADMIN = 5 DEBUG = 6 EXPERIMENTAL = 7 # Feature names for display FEATURE_NAMES = { DARK_MODE: "Dark Mode", NOTIFICATIONS: "Notifications", BETA_FEATURES: "Beta Features", ANALYTICS: "Analytics", PREMIUM: "Premium", ADMIN: "Admin", DEBUG: "Debug", EXPERIMENTAL: "Experimental", } def __init__(self, initial_flags: int = 0): self._flags = initial_flags def enable(self, feature: int) -> None: """Enable a feature.""" self._flags |= (1 << feature) def disable(self, feature: int) -> None: """Disable a feature.""" self._flags &= ~(1 << feature) def toggle(self, feature: int) -> None: """Toggle a feature.""" self._flags ^= (1 << feature) def is_enabled(self, feature: int) -> bool: """Check if a feature is enabled.""" return (self._flags & (1 << feature)) != 0 def set_all(self, features: list[int]) -> None: """Enable multiple features, disable all others.""" self._flags = 0 for f in features: self._flags |= (1 << f) def to_dict(self) -> dict: """Export as dictionary for debugging/serialization.""" return { name: self.is_enabled(feature) for feature, name in self.FEATURE_NAMES.items() } @property def raw_value(self) -> int: """Get raw integer value (for storage/transmission).""" return self._flags @classmethod def from_raw(cls, value: int) -> 'FeatureFlags': """Create from raw integer (from storage/transmission).""" return cls(value) def __str__(self) -> str: enabled = [name for feature, name in self.FEATURE_NAMES.items() if self.is_enabled(feature)] return f"Features({format(self._flags, '08b')}): {enabled}" # Demonstrationprint("=== Feature Flag System ===") # Create default user flagsuser = FeatureFlags()print(f"New user: {user}") # Enable some featuresuser.enable(FeatureFlags.DARK_MODE)user.enable(FeatureFlags.NOTIFICATIONS)user.enable(FeatureFlags.ANALYTICS)print(f"After setup: {user}") # Check specific featureprint(f"Dark mode enabled? {user.is_enabled(FeatureFlags.DARK_MODE)}")print(f"Premium enabled? {user.is_enabled(FeatureFlags.PREMIUM)}") # User upgrades to premiumuser.enable(FeatureFlags.PREMIUM)user.enable(FeatureFlags.BETA_FEATURES)print(f"After upgrade: {user}") # Serialize for storageraw = user.raw_valueprint(f"Serialized value: {raw} (0x{raw:02X})") # Restore from storagerestored = FeatureFlags.from_raw(raw)print(f"Restored: {restored}") # Feature rollbackuser.disable(FeatureFlags.BETA_FEATURES)print(f"After rollback: {user}") # Full exportprint(f"Full state: {user.to_dict()}")Let's consolidate everything we've learned across this module into a comprehensive reference:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159
"""Complete Bit Manipulation Cheat Sheet===================================== This module contains all fundamental bit manipulation operationsorganized by category.""" # ============================================# BASIC BIT OPERATIONS# ============================================ def is_even(n: int) -> bool: """Check if n is even.""" return (n & 1) == 0 def is_odd(n: int) -> bool: """Check if n is odd.""" return (n & 1) == 1 # ============================================# RIGHTMOST SET BIT OPERATIONS# ============================================ def rightmost_set_bit(n: int) -> int: """Extract (isolate) the rightmost set bit.""" return n & -n def clear_rightmost_set_bit(n: int) -> int: """Clear (remove) the rightmost set bit.""" return n & (n - 1) def count_set_bits(n: int) -> int: """Count set bits using Brian Kernighan's algorithm.""" count = 0 while n: n = n & (n - 1) count += 1 return count def is_power_of_two(n: int) -> bool: """Check if n is a power of 2.""" return n > 0 and (n & (n - 1)) == 0 # ============================================# SINGLE BIT AT POSITION k# ============================================ def get_bit(n: int, k: int) -> int: """Get the value (0 or 1) of bit at position k.""" return (n >> k) & 1 def is_bit_set(n: int, k: int) -> bool: """Check if bit at position k is set.""" return (n & (1 << k)) != 0 def set_bit(n: int, k: int) -> int: """Set bit at position k to 1.""" return n | (1 << k) def clear_bit(n: int, k: int) -> int: """Clear bit at position k (set to 0).""" return n & ~(1 << k) def toggle_bit(n: int, k: int) -> int: """Toggle bit at position k.""" return n ^ (1 << k) def update_bit(n: int, k: int, v: int) -> int: """Update bit at position k to value v (0 or 1).""" return (n & ~(1 << k)) | (v << k) # ============================================# BIT RANGE OPERATIONS# ============================================ def extract_bits(n: int, start: int, width: int) -> int: """Extract 'width' bits starting at position 'start'.""" mask = (1 << width) - 1 return (n >> start) & mask def clear_lower_bits(n: int, k: int) -> int: """Clear the lowest k bits.""" return n & ~((1 << k) - 1) def set_lower_bits(n: int, k: int) -> int: """Set the lowest k bits to 1.""" return n | ((1 << k) - 1) def toggle_lower_bits(n: int, k: int) -> int: """Toggle the lowest k bits.""" return n ^ ((1 << k) - 1) # ============================================# ADVANCED OPERATIONS# ============================================ def swap_bits(n: int, i: int, j: int) -> int: """Swap bits at positions i and j.""" if ((n >> i) & 1) != ((n >> j) & 1): n ^= (1 << i) | (1 << j) return n def reverse_bits(n: int, width: int = 32) -> int: """Reverse bits within the given width.""" result = 0 for i in range(width): if (n >> i) & 1: result |= 1 << (width - 1 - i) return result def next_power_of_two(n: int) -> int: """Find the smallest power of 2 >= n.""" if n <= 0: return 1 if is_power_of_two(n): return n n -= 1 n |= n >> 1 n |= n >> 2 n |= n >> 4 n |= n >> 8 n |= n >> 16 return n + 1 # ============================================# DEMO# ============================================ if __name__ == "__main__": print("Bit Manipulation Cheat Sheet Demo") print("=" * 50) n = 42 # 00101010 print(f"Working with n = {n} ({format(n, '08b')})") print(f"Basic checks:") print(f" is_even({n}) = {is_even(n)}") print(f" is_power_of_two({n}) = {is_power_of_two(n)}") print(f" count_set_bits({n}) = {count_set_bits(n)}") print(f"Bit operations at position 3:") print(f" get_bit({n}, 3) = {get_bit(n, 3)}") print(f" set_bit({n}, 3) = {set_bit(n, 3)} ({format(set_bit(n, 3), '08b')})") print(f" clear_bit({n}, 3) = {clear_bit(n, 3)} ({format(clear_bit(n, 3), '08b')})") print(f" toggle_bit({n}, 3) = {toggle_bit(n, 3)} ({format(toggle_bit(n, 3), '08b')})") print(f"Rightmost set bit:") print(f" rightmost_set_bit({n}) = {rightmost_set_bit(n)}") print(f" clear_rightmost_set_bit({n}) = {clear_rightmost_set_bit(n)}")Congratulations! You've completed the Common Bit Manipulation Tricks module. You now have a comprehensive toolkit for manipulating individual bits in integers. Let's consolidate the key insights:
n | (1 << k) — OR with mask adds a 1 at position k.n & ~(1 << k) — AND with inverted mask removes the bit at position k.n ^ (1 << k) — XOR with mask flips the bit at position k.(n & ~(1<<k)) | (v<<k) — Clear then set to write a specific value.Module Complete:
This module covered the five core bit manipulation tricks:
With these building blocks, you can implement virtually any bit manipulation algorithm. The next module in this chapter will cover checking, setting, clearing, and toggling bits in more depth, including multi-bit operations and common interview patterns.
You now have a complete toolkit for common bit manipulation. These techniques appear constantly in systems programming, competitive programming, and technical interviews. Practice these operations until they become second nature—they'll serve you throughout your programming career.