Bitwise Operators - The Systems Programmer's Toolkit

Reading time: ~25 minutes | Level: Foundation → Engineering

What does this code print, and can you explain every digit?

permissions = 0o755
print(f"owner:  r={bool(permissions & 0o400)}, w={bool(permissions & 0o200)}, x={bool(permissions & 0o100)}")
print(f"group:  r={bool(permissions & 0o040)}, w={bool(permissions & 0o020)}, x={bool(permissions & 0o010)}")
print(f"others: r={bool(permissions & 0o004)}, w={bool(permissions & 0o002)}, x={bool(permissions & 0o001)}")

n = 42
print(n & 1)         # even/odd check
print(n >> 1)        # fast integer halving
print(n ^ n)         # always 0
print(~n)            # what is this?

If any of those confused you - or if you have only seen bitwise operators as "advanced/esoteric" - this lesson changes that. Bitwise operators connect Python to hardware. They are how operating systems manage permissions, how networking code reads packet headers, how cryptographic primitives mix bits, and how you write memory-efficient flag systems. Every systems-oriented Python engineer needs them.

What You Will Learn

Why bitwise operators exist and where they appear in real engineering systems
How Python represents integers in binary, and how arbitrary-precision integers affect two's complement
All six bitwise operators with truth tables, ASCII bit diagrams, and worked examples
Practical masking patterns: checking, setting, clearing, and toggling individual bits
The bit flags pattern - representing multiple boolean states in a single integer
Unix permission bits decoded with bitwise operations
Real-world engineering tricks: even/odd check, power-of-two division with shifts, XOR swap, and finding the unique element
Python's bin(), hex(), oct() for visualization and debugging
The enum.Flag class - Python's structured way to work with bit flags
Precedence pitfalls and the difference between bitwise & and logical and

Prerequisites

Python integers and variables (Lesson 03)
Arithmetic operators (Lesson 08)
Basic understanding that integers are stored as binary in hardware

Part 1 - Why Bitwise Operators Exist

High-level code deals with names, objects, and abstractions. But beneath every abstraction, a CPU manipulates bits - the binary digits 0 and 1 from which all data is built. Bitwise operators let you work at that level when you need to.

Real engineering domains that use bitwise operations constantly:

Operating systems: Unix file permissions (chmod 755) are three groups of three bits each
Networking: IP addresses, subnet masks, TCP flags, port numbers - all extracted and set with bitwise operations
Cryptography: XOR is the foundation of stream ciphers, one-time pads, and many hash mixing steps
Data compression: Huffman coding, LZ77, and bitmap compression all pack data at the bit level
Embedded systems / hardware drivers: Registers are bit fields; setting or reading a hardware pin is a single masked bit write
Database engines: PostgreSQL's pg_attribute.atttypmod, null bitmaps in row headers, index bitmaps
Graphics: Pixel colors in ARGB format (0xAARRGGBB) are extracted with shifts and masks
Performance code: Replacing division and modulo with shifts and masks in tight inner loops

Python is not a systems language, but Python engineers regularly interface with C libraries, parse binary protocols, and implement algorithms where understanding bits is non-negotiable.

Part 2 - Binary Number Representation

Positional Notation

Every integer has an exact representation in binary. Binary is base-2: each position represents a power of 2, compared to base-10 where each position represents a power of 10.

Decimal 13 in binary:

Position:  3    2    1    0
Power:     2³   2²   2¹   2⁰
Value:      8    4    2    1
Bit:        1    1    0    1

1×8 + 1×4 + 0×2 + 1×1 = 13
Binary: 1101

Python gives you three ways to write integer literals directly in non-decimal bases:

# These are all the same integer:
decimal     = 13
binary      = 0b1101       # prefix 0b
octal       = 0o15         # prefix 0o
hexadecimal = 0xD          # prefix 0x

print(decimal == binary == octal == hexadecimal)   # True

And three built-in functions to display integers in different bases:

n = 42
print(bin(n))              # '0b101010'
print(oct(n))              # '0o52'
print(hex(n))              # '0x2a'
print(format(n, '08b'))    # '00101010'  - zero-padded to 8 bits
print(format(n, '#010b'))  # '0b00101010' - with prefix, total 10 chars

Two's Complement and Negative Integers

In fixed-width systems (C int, hardware registers), negative numbers are stored in two's complement: flip all bits, then add 1.

In an 8-bit system:
  5  =  0000 0101
 ~5  =  1111 1010   (flip all bits)
 -5  =  1111 1011   (add 1) ← two's complement of 5

The leftmost bit is the sign bit: 0 means positive, 1 means negative.

Python integers are arbitrary precision - they are not stored in a fixed-width register. Internally, CPython stores large integers as an array of 30-bit or 15-bit "digits." There is no fixed sign bit and no overflow. However, Python's bitwise operators are defined to behave as if integers use infinite-width two's complement, with an infinite string of 0 bits extending left for positive numbers and an infinite string of 1 bits extending left for negative numbers.

# Conceptual infinite-width two's complement:
#  5 = ...0000 0000 0101   (infinite zeros to the left)
# -5 = ...1111 1111 1011   (infinite ones to the left)

print(bin(5))     # 0b101
print(bin(-5))    # -0b101  ← Python displays negative as -0b<magnitude>
                  # but bitwise operations use two's complement semantics

This infinite model has one important consequence: ~n for Python integers.

Part 3 - The Six Bitwise Operators

Truth Tables

AND, OR, XOR:

A	B	A & B	A \| B	A ^ B
0	0	0	0	0
0	1	0	1	1
1	0	0	1	1
1	1	1	1	0

NOT:

A	~A
0	1
1	0

Operator 1: `&` - Bitwise AND (Masking)

AND produces 1 only where both inputs are 1. It is used to read (mask) specific bits while zeroing out all others.

a = 0b1101   # 13
b = 0b1011   # 11

result = a & b
print(bin(result))   # 0b1001  = 9

  1 1 0 1   (13)
& 1 0 1 1   (11)
-----------
  1 0 0 1   (9) - only positions where BOTH were 1

Masking pattern - read a specific bit:

value = 0b10110100

# Is bit 4 set? (counting from 0 on the right)
mask = 1 << 4           # 0b00010000
is_set = bool(value & mask)
print(is_set)           # True

# Extract the lower 4 bits (nibble):
lower_nibble = value & 0b00001111   # or & 0xF
print(bin(lower_nibble))             # 0b100

Operator 2: `|` - Bitwise OR (Setting Bits)

OR produces 1 wherever either input is 1. It is used to set (turn on) specific bits without affecting others.

value = 0b10000000   # only bit 7 set

# Set bit 2:
value = value | (1 << 2)
print(bin(value))   # 0b10000100

# Set multiple bits at once:
FLAGS = 0b00000001 | 0b00000100 | 0b00010000
print(bin(FLAGS))   # 0b10101  - bits 0, 2, and 4 are set

  1 0 0 0 0 0 0 0   (128)
| 0 0 0 0 0 1 0 0   (4)
-----------------
  1 0 0 0 0 1 0 0   (132) - bit 2 is now on

Operator 3: `^` - Bitwise XOR (Toggling and Differencing)

XOR produces 1 where inputs differ. XOR with a 1-bit toggles that bit; XOR with a 0-bit leaves it unchanged.

value = 0b11001010

# Toggle bits 1 and 3:
toggle_mask = 0b00001010
value ^= toggle_mask
print(bin(value))   # 0b11000000  - bits 1 and 3 flipped

  1 1 0 0 1 0 1 0
^ 0 0 0 0 1 0 1 0
-----------------
  1 1 0 0 0 0 0 0   - only differing positions become 1

Identity property of XOR: x ^ x == 0 for any value. This is used to detect changes, implement checksums, and initialize accumulators.

Operator 4: `~` - Bitwise NOT (Complement)

NOT flips every bit. In Python's infinite two's complement model, flipping all bits of n gives you -(n+1).

print(~5)    # -6
print(~0)    # -1
print(~-1)   # 0
print(~100)  # -101

The formula is: ~n == -(n + 1), always, for any Python integer.

Why ~5 = -6:
  ...0000 0101   (5, infinite zeros to the left)
  ...1111 1010   (flip all bits)
= -6 in two's complement (infinite ones = -1, then adjusting)

warning

~n in Python is not the same as C's bitwise NOT. In C with uint32_t, ~5u gives 4294967290 (flipping 32 bits). In Python, ~5 gives -6 because Python integers have infinite precision and ~ follows infinite two's complement semantics. Code that ports C bit manipulation to Python must account for this difference.

Practical use of ~ - clearing bits (AND NOT pattern):

value = 0b11111111

# Clear bit 3 (set it to 0):
bit_to_clear = 1 << 3      # 0b00001000
value = value & ~bit_to_clear
print(bin(value))           # 0b11110111

Operator 5: `<<` - Left Shift (Multiply by Powers of 2)

Left shift moves all bits toward higher positions, filling the vacated low bits with 0. Shifting left by n positions multiplies the integer by 2**n.

print(1 << 0)    # 1
print(1 << 1)    # 2
print(1 << 2)    # 4
print(1 << 3)    # 8
print(1 << 10)   # 1024
print(7 << 2)    # 28  (7 * 4)

  0 0 0 0 0 1 1 1   (7)
<< 2
  0 0 0 1 1 1 0 0   (28) - all bits moved 2 positions left

Left shift is how you construct bitmasks efficiently:

# Create a mask for bit position n:
def bit_mask(n: int) -> int:
    return 1 << n

print(bit_mask(0))   # 1   = 0b00000001
print(bit_mask(4))   # 16  = 0b00010000
print(bit_mask(7))   # 128 = 0b10000000

Operator 6: `>>` - Right Shift (Arithmetic Divide by Powers of 2)

Right shift moves all bits toward lower positions. For positive integers, vacated high bits fill with 0. For negative integers (two's complement), Python uses arithmetic right shift - the sign bit is preserved (vacated high bits fill with 1).

print(100 >> 1)    # 50   (100 / 2)
print(100 >> 2)    # 25   (100 / 4)
print(100 >> 3)    # 12   (100 / 8, floor division)

# Negative numbers - sign bit extends:
print(-8 >> 1)     # -4   (floor(-8/2) = -4)
print(-7 >> 1)     # -4   (floor(-7/2) = -4, not -3)

  0 1 1 0 0 1 0 0   (100)
>> 2
  0 0 0 1 1 0 0 1   (25) - bits moved right, zeros fill from left

This arithmetic right shift behavior is identical to // for powers of 2:

n = 100
print(n >> 3)     # 12
print(n // 8)     # 12  - same result

note

In Python, n >> k and n // (2**k) produce identical results for all integers, including negatives (both floor toward negative infinity). Some languages have both arithmetic shift (sign-extending) and logical shift (zero-filling) - Python only has arithmetic shift.

Part 4 - The Bit Flags Pattern

Integers as Sets of Booleans

A single Python integer can store multiple boolean states, one per bit. This is more memory-efficient than a dictionary, faster to test than a list, and composable with | and &.

The pattern:

# Define each flag as a power of 2 (one bit each):
READ    = 1 << 0   # 0b00000001 = 1
WRITE   = 1 << 1   # 0b00000010 = 2
EXECUTE = 1 << 2   # 0b00000100 = 4
ADMIN   = 1 << 3   # 0b00001000 = 8
AUDIT   = 1 << 4   # 0b00010000 = 16

Bit position	7	6	5	4	3	2	1	0
Flag	.	.	.	AUDIT	ADMIN	EXEC	WRITE	READ

# Combine flags with | (set multiple bits on):
alice_perms = READ | WRITE | EXECUTE   # 0b111 = 7
bob_perms   = READ | ADMIN             # 0b1001 = 9

# Test a single flag with & (mask all other bits off):
def has_permission(perms: int, flag: int) -> bool:
    return bool(perms & flag)

print(has_permission(alice_perms, READ))     # True
print(has_permission(alice_perms, ADMIN))    # False
print(has_permission(bob_perms, ADMIN))      # True
print(has_permission(bob_perms, WRITE))      # False

# Grant a permission:
alice_perms |= AUDIT    # set AUDIT bit

# Revoke a permission (AND NOT):
alice_perms &= ~WRITE   # clear WRITE bit

# Toggle a permission:
bob_perms ^= EXECUTE    # flip EXECUTE bit

Unix File Permissions - The Classic Example

Unix file permissions (rwxrwxrwx) are nine bits: three groups (owner, group, others), each with three flags (read=4, write=2, execute=1).

# chmod 755 means:
# Owner: rwx = 4+2+1 = 7
# Group: r-x = 4+0+1 = 5
# Others: r-x = 4+0+1 = 5

permissions = 0o755   # octal literal

# Masks for each triplet:
OWNER_READ    = 0o400
OWNER_WRITE   = 0o200
OWNER_EXECUTE = 0o100
GROUP_READ    = 0o040
GROUP_WRITE   = 0o020
GROUP_EXECUTE = 0o010
OTHER_READ    = 0o004
OTHER_WRITE   = 0o002
OTHER_EXECUTE = 0o001

def decode_permissions(perm: int) -> str:
    chars = [
        'r' if perm & OWNER_READ    else '-',
        'w' if perm & OWNER_WRITE   else '-',
        'x' if perm & OWNER_EXECUTE else '-',
        'r' if perm & GROUP_READ    else '-',
        'w' if perm & GROUP_WRITE   else '-',
        'x' if perm & GROUP_EXECUTE else '-',
        'r' if perm & OTHER_READ    else '-',
        'w' if perm & OTHER_WRITE   else '-',
        'x' if perm & OTHER_EXECUTE else '-',
    ]
    return ''.join(chars)

print(decode_permissions(0o755))   # rwxr-xr-x
print(decode_permissions(0o644))   # rw-r--r--
print(decode_permissions(0o600))   # rw-------

This is exactly what Python's os.stat() and stat module implement:

import os, stat

info = os.stat("/etc/passwd")
mode = info.st_mode

print(bool(mode & stat.S_IRUSR))   # owner can read?
print(bool(mode & stat.S_IWGRP))   # group can write?
print(oct(stat.S_IMODE(mode)))     # e.g., '0o644'

Part 5 - Engineering Tricks and Algorithms

Even/Odd Detection Without Division

The lowest bit of any integer is 1 for odd numbers and 0 for even numbers:

def is_even(n: int) -> bool:
    return (n & 1) == 0

def is_odd(n: int) -> bool:
    return bool(n & 1)

print(is_even(42))    # True
print(is_odd(17))     # True
print(is_even(-4))    # True
print(is_odd(-3))     # True

At the CPU level, this is a single AND instruction - faster than integer division by 2.

Power-of-Two Check

An integer n is a power of 2 if and only if it has exactly one bit set. The trick n & (n - 1) clears the lowest set bit - so for powers of 2, the result is always 0:

def is_power_of_two(n: int) -> bool:
    return n > 0 and (n & (n - 1)) == 0

print(is_power_of_two(1))    # True  (2^0)
print(is_power_of_two(8))    # True  (2^3)
print(is_power_of_two(12))   # False
print(is_power_of_two(0))    # False
print(is_power_of_two(-4))   # False

# Why it works:
# 8  = 0b01000
# 7  = 0b00111
# 8 & 7 = 0b00000 = 0  ← only bit cleared is the single set bit

XOR Tricks

The XOR swap - swapping two values without a temporary variable:

a, b = 5, 9
a ^= b    # a = 5 ^ 9 = 12
b ^= a    # b = 9 ^ 12 = 5  (original a)
a ^= b    # a = 12 ^ 5 = 9  (original b)
print(a, b)   # 9 5  - swapped

# Why it works:
# a ^ b ^ b == a  (XOR is its own inverse)
# a ^ b ^ a == b

note

The XOR swap is a classic interview trick and a demonstration of XOR's self-inverse property. In Python, the idiomatic swap is a, b = b, a. Use the XOR swap only when you are specifically teaching or demonstrating bitwise properties - Python's tuple swap is clearer and equally fast.

Finding the unique element - every number appears twice except one:

def find_unique(nums: list) -> int:
    result = 0
    for n in nums:
        result ^= n
    return result

data = [3, 1, 4, 1, 3]
print(find_unique(data))   # 4

# Why it works:
# Pairs cancel out: x ^ x == 0
# Zero is identity: 0 ^ x == x
# Order doesn't matter: XOR is commutative and associative
# 3^1^4^1^3 = (3^3)^(1^1)^4 = 0^0^4 = 4

This is an O(n) time, O(1) space solution - common in coding interviews.

Fast Multiplication/Division by Powers of 2

n = 100
print(n << 1)    # 200  (n * 2)
print(n << 3)    # 800  (n * 8)
print(n >> 1)    # 50   (n // 2)
print(n >> 2)    # 25   (n // 4)

# Extracting a byte from a 32-bit integer:
color = 0xFF5733   # RGB: R=255, G=87, B=51
r = (color >> 16) & 0xFF
g = (color >> 8)  & 0xFF
b = (color >> 0)  & 0xFF
print(r, g, b)   # 255 87 51

The extraction pattern (value >> shift) & mask is ubiquitous in binary protocol parsing: extract bits, shift them to position 0, then mask to width.

Counting Set Bits (Popcount)

def popcount(n: int) -> int:
    """Count the number of 1-bits in n."""
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count

print(popcount(0b10110101))   # 5

# Python 3.10+ has this built in:
print((0b10110101).bit_count())   # 5

# Find the position of the highest set bit:
n = 100
print(n.bit_length())   # 7 (because 100 = 0b1100100, 7 digits)

Part 6 - Python Stdlib and Bitwise Operations

`enum.Flag` - Structured Bit Flags

Python's standard library provides enum.Flag for type-safe, self-documenting bit flags:

from enum import Flag, auto

class Permission(Flag):
    READ    = auto()   # auto() assigns successive powers of 2: 1, 2, 4, ...
    WRITE   = auto()
    EXECUTE = auto()
    ADMIN   = auto()

# Combine with |:
alice = Permission.READ | Permission.WRITE | Permission.EXECUTE
bob   = Permission.READ | Permission.ADMIN

# Test membership with &:
print(Permission.READ in alice)    # True
print(Permission.ADMIN in alice)   # False
print(Permission.ADMIN in bob)     # True

# Readable string representation:
print(alice)   # Permission.READ|WRITE|EXECUTE
print(bob)     # Permission.READ|ADMIN

# Remove a permission with & ~:
alice &= ~Permission.WRITE
print(alice)   # Permission.READ|EXECUTE

enum.Flag is the recommended way to implement bit flag systems in production Python code. It gives you type safety, readable repr, iteration over set flags, and all bitwise operations automatically.

Socket and OS Flags

Python's socket and os modules use bitwise flags extensively:

import socket

# Socket creation flags - combined with |:
sock = socket.socket(
    family=socket.AF_INET,
    type=socket.SOCK_STREAM | socket.SOCK_NONBLOCK
)

# OS open flags:
import os
fd = os.open("/tmp/test.txt", os.O_RDWR | os.O_CREAT | os.O_TRUNC, 0o644)
os.close(fd)

# These flags are just integers defined in the module:
print(socket.SOCK_STREAM)    # 1
print(socket.SOCK_NONBLOCK)  # 2048 (platform-dependent)

Part 7 - Visualization and Debugging

When working with bitwise operations, always visualize:

def show_bits(n: int, width: int = 8, label: str = "") -> None:
    """Display an integer as a zero-padded binary string with label."""
    if n < 0:
        # Show conceptual two's complement for small negative numbers
        bits = format(n & ((1 << width) - 1), f'0{width}b')
    else:
        bits = format(n, f'0{width}b')
    groups = ' '.join(bits[i:i+4] for i in range(0, len(bits), 4))
    print(f"{label:12s} = {groups}  ({n})")

show_bits(42,       label="42     ")   # 42      = 0010 1010  (42)
show_bits(0xFF,     label="0xFF   ")   # 0xFF    = 1111 1111  (255)
show_bits(42 & 15,  label="42 & 15")   # 42 & 15 = 0000 1010  (10)
show_bits(42 | 1,   label="42 | 1 ")   # 42 | 1  = 0010 1011  (43)
show_bits(42 ^ 42,  label="42 ^ 42")   # 42 ^ 42 = 0000 0000  (0)

For debugging binary protocols, format(value, '#010x') gives zero-padded hex, and format(value, '#034b') gives zero-padded binary with prefix.

Part 8 - Pitfalls and Common Mistakes

Pitfall 1: `~n` Is Not Unsigned NOT

Engineers from C or JavaScript expect ~5 to be a large positive number (all 32 bits flipped from 0000...0101). In Python:

import ctypes

# C behavior (simulated):
c_result = ctypes.c_uint32(~5).value
print(c_result)    # 4294967290  (all 32 bits flipped)

# Python behavior:
print(~5)          # -6          (infinite two's complement)

# To emulate C's unsigned 32-bit NOT in Python:
mask_32 = 0xFFFFFFFF
result = (~5) & mask_32
print(result)      # 4294967290

If you are implementing a C algorithm in Python that uses ~ on unsigned values, always AND with the appropriate width mask afterward.

Pitfall 2: Operator Precedence - `&` Is Lower Than `==`

This surprises almost every engineer transitioning from C:

# What is the intent here?
n = 4
print(n & 3 == 0)   # True or False?

# Python parses it as:
print(n & (3 == 0))   # n & False = n & 0 = 0 → False!

# What was intended:
print((n & 3) == 0)   # True  - n=4=0b100; 4 & 3 = 0b100 & 0b011 = 0

The precedence hierarchy for bitwise and comparison operators:

Higher (evaluated first)
  ~           (unary NOT)
  <<, >>      (shifts)
  &           (AND)
  ^           (XOR)
  |           (OR)
  ==, !=, <, >, <=, >=  (comparisons)
Lower (evaluated last)

Wait - & has higher precedence than == in Python! So n & 3 == 0 actually parses as (n & 3) == 0. Let's verify:

n = 4
print(n & 3 == 0)    # (4 & 3) == 0 = 0 == 0 = True

But this is still confusing to read. Always use explicit parentheses when mixing bitwise and comparison operators - clarity is more valuable than saved keystrokes:

# Unambiguous:
if (value & FLAG) != 0:
    ...
if (n & (n - 1)) == 0:
    ...

danger

Do not use bitwise & and | in place of logical and and or. This is a critical correctness bug:

# WRONG - bitwise AND on booleans, no short-circuit:
if user_is_active & has_permission:   # evaluates BOTH sides always
    ...

# WRONG - may call has_permission(user) even when user is None:
if user & has_permission(user):   # TypeError if user is None

# CORRECT - logical and, short-circuits:
if user_is_active and has_permission:
    ...

Bitwise operators always evaluate both operands. They never short-circuit. Using them where you meant logical operators silently removes short-circuit safety guards.

Pitfall 3: Large Shifts Are Legal but Expensive

Python's arbitrary-precision integers mean large shifts simply produce large numbers rather than overflow:

print(1 << 1000)   # A 302-digit integer - valid, but allocates memory
print(1 << 10000)  # Larger still - valid but slow

In a tight loop over large data, an accidentally large shift is a performance bug. Validate shift amounts against your expected bit width.

Pitfall 4: Right-Shifting Does Not Work for Extracting the "Unsigned" High Bits of Negative Numbers

n = -1
print(n >> 4)   # -1  - sign bit extends, stays -1 forever

There is no logical (unsigned) right shift in Python. To emulate it, mask to the desired width first:

n = -1
width = 32
unsigned_n = n & 0xFFFFFFFF    # Treat as 32-bit unsigned
print(unsigned_n >> 4)         # 268435455  (0x0FFFFFFF)

Interview Questions

Q1: You have a list of integers where every element appears exactly twice except one. Find the unique element in O(n) time and O(1) space.

XOR every element together. Pairs cancel out because x ^ x == 0 and XOR is commutative and associative. The lone unpaired element remains. result = 0; for n in nums: result ^= n; return result. This runs in O(n) time with O(1) extra space. It is a textbook demonstration of XOR's self-inverse property.

Q2: How do you check whether bit k is set in integer n?

bool(n & (1 << k)). The expression 1 << k creates a mask with only bit k set. ANDing with n zeroes all other bits, leaving either 2**k (bit was set) or 0 (bit was clear). Always parenthesize: (n & (1 << k)) != 0 is clear and unambiguous.

Q3: What does ~n return in Python, and how does this differ from C?

In Python, ~n always returns -(n+1). For n=5, ~5 == -6. This is because Python integers are modeled as infinite-width two's complement, so flipping all infinite bits of a positive number produces a negative number whose magnitude is n+1. In C with a uint32_t, ~5u flips all 32 bits, giving 4294967290. To emulate C's unsigned NOT in Python, use (~n) & 0xFFFFFFFF (or the appropriate mask for your bit width).

Q4: Why do networking and cryptography code use bitwise XOR so heavily?

XOR has several properties that make it invaluable: (1) It is its own inverse: (a ^ b) ^ b == a, so XOR-based encryption is trivially reversible. (2) It mixes bits without carry propagation, unlike addition, making it fast and avalanche-free in isolation. (3) A uniform random key XORed with any plaintext produces statistically uniform output - the basis of one-time pads and stream ciphers. (4) XOR is a single CPU instruction on all architectures. In network checksums, XOR-based folding of 16-bit words builds IP and TCP checksums efficiently.

Q5: What is the difference between n >> k and n // (2**k) for negative integers in Python?

They produce identical results for all integers, including negatives, because Python's right shift is arithmetic (sign-extending) and floors toward negative infinity - the same behavior as //. Both (-7) >> 1 and (-7) // 2 give -4. This contrasts with C, where signed right shift behavior for negatives is implementation-defined (some compilers implement it as arithmetic, some as logical). In Python you can use them interchangeably for powers of 2, but >> is typically faster for constant shift amounts.

Q6: When would you use enum.Flag instead of raw integer bit flags?

Use enum.Flag in production application code where readability, type safety, and iteration over set flags matter. enum.Flag gives you named members (no magic numbers like 4 meaning "execute"), a readable repr, membership testing with in, and automatic combination via |. Use raw integer bit flags when: interfacing directly with C libraries or binary protocols that hand you raw integer values, writing low-level parsers where you control the specific bit positions, or in performance-critical inner loops where the overhead of enum.Flag member creation is measurable. Both approaches use the same bitwise operators underneath.

Graded Practice Challenges

Level 1 - Predict the Output

print(bin(0b1010 & 0b1100))
print(bin(0b1010 | 0b1100))
print(bin(0b1010 ^ 0b1100))
print(~42)
print(1 << 5)
print(100 >> 2)
print(0b10110101.bit_count() if hasattr(int, 'bit_count') else bin(0b10110101).count('1'))

Show Answer

0b1010 & 0b1100:
   1010
 & 1100
 ------
   1000   → bin(8) = '0b1000'

0b1010 | 0b1100:
   1010
 | 1100
 ------
   1110   → bin(14) = '0b1110'

0b1010 ^ 0b1100:
   1010
 ^ 1100
 ------
   0110   → bin(6) = '0b110'

~42  = -(42+1) = -43

1 << 5 = 32

100 >> 2 = 25  (100 // 4 = 25)

0b10110101 = 5 set bits (1+0+1+1+0+1+0+1) → 5

Level 2 - Debug the Bug

A developer wrote this function to extract the red, green, and blue channels from a 24-bit RGB color integer. The function has two bugs. Find and fix them:

def extract_rgb(color: int):
    # color is 0xRRGGBB - 24 bits
    r = color >> 8 & 0xFF    # Bug 1
    g = color >> 8 & 0xFF
    b = color & 0xFF
    return r, g, b

print(extract_rgb(0xFF5733))   # Should be (255, 87, 51)

Show Answer

Bug 1: The red channel should be extracted by shifting 16 bits right, not 8. The formula should be (color >> 16) & 0xFF.

Bug 2: The green channel shift is correct at 8, but the parentheses are missing. Due to precedence, color >> 8 & 0xFF is parsed as color >> (8 & 0xFF) - wait, actually >> has higher precedence than &, so it parses as (color >> 8) & 0xFF. That is actually correct for green. The real bug is only that r uses shift 8 instead of shift 16.

def extract_rgb(color: int):
    r = (color >> 16) & 0xFF   # fixed: shift 16 for red
    g = (color >> 8)  & 0xFF   # correct: shift 8 for green
    b = (color >> 0)  & 0xFF   # correct: no shift for blue
    return r, g, b

print(extract_rgb(0xFF5733))   # (255, 87, 51)

Key insight: in a packed 0xRRGGBB integer, red is in bits 23-16 (shift right 16), green in bits 15-8 (shift right 8), blue in bits 7-0 (no shift). Always mask with 0xFF after shifting to discard any higher-order bits.

Level 3 - Design

Design a Python class PermissionSystem that implements a role-based permission system using bit flags. Requirements:

Define at least five distinct permissions as class-level constants using 1 << n notation.
Implement methods: grant(user_id, permission), revoke(user_id, permission), toggle(user_id, permission), has(user_id, permission) -> bool, list_permissions(user_id) -> list[str].
Store permissions per user in a dictionary (user_id → integer bitmask).
list_permissions must return human-readable names, not integers.
Demonstrate: grant multiple permissions, test them, revoke one, verify revocation, toggle, and list.

Show Answer

class PermissionSystem:
    # Define permissions as consecutive bits:
    READ     = 1 << 0   # 1
    WRITE    = 1 << 1   # 2
    DELETE   = 1 << 2   # 4
    ADMIN    = 1 << 3   # 8
    AUDIT    = 1 << 4   # 16

    # Name lookup for human-readable output:
    _NAMES = {
        READ:   "READ",
        WRITE:  "WRITE",
        DELETE: "DELETE",
        ADMIN:  "ADMIN",
        AUDIT:  "AUDIT",
    }

    def __init__(self):
        self._permissions: dict[str, int] = {}

    def _get(self, user_id: str) -> int:
        return self._permissions.get(user_id, 0)

    def grant(self, user_id: str, permission: int) -> None:
        """Set the permission bit using OR."""
        self._permissions[user_id] = self._get(user_id) | permission

    def revoke(self, user_id: str, permission: int) -> None:
        """Clear the permission bit using AND NOT."""
        self._permissions[user_id] = self._get(user_id) & ~permission

    def toggle(self, user_id: str, permission: int) -> None:
        """Flip the permission bit using XOR."""
        self._permissions[user_id] = self._get(user_id) ^ permission

    def has(self, user_id: str, permission: int) -> bool:
        """Check if a specific bit is set using AND."""
        return bool(self._get(user_id) & permission)

    def list_permissions(self, user_id: str) -> list:
        """Return human-readable names of all granted permissions."""
        mask = self._get(user_id)
        return [
            name for flag, name in self._NAMES.items()
            if mask & flag
        ]


# Demonstration:
ps = PermissionSystem()

# Grant permissions:
ps.grant("alice", PermissionSystem.READ | PermissionSystem.WRITE | PermissionSystem.DELETE)
ps.grant("bob", PermissionSystem.READ | PermissionSystem.ADMIN)

print("Alice:", ps.list_permissions("alice"))
# ['READ', 'WRITE', 'DELETE']
print("Bob:", ps.list_permissions("bob"))
# ['READ', 'ADMIN']

# Test:
print(ps.has("alice", PermissionSystem.ADMIN))   # False
print(ps.has("bob", PermissionSystem.ADMIN))     # True

# Revoke DELETE from Alice:
ps.revoke("alice", PermissionSystem.DELETE)
print("Alice after revoke:", ps.list_permissions("alice"))
# ['READ', 'WRITE']

# Toggle AUDIT on Alice (was off → now on):
ps.toggle("alice", PermissionSystem.AUDIT)
print("Alice after toggle:", ps.list_permissions("alice"))
# ['READ', 'WRITE', 'AUDIT']

# Toggle AUDIT again (now on → off):
ps.toggle("alice", PermissionSystem.AUDIT)
print("Alice after toggle again:", ps.list_permissions("alice"))
# ['READ', 'WRITE']

# Grant multiple at once using |:
ps.grant("carol", PermissionSystem.READ | PermissionSystem.ADMIN | PermissionSystem.AUDIT)
print("Carol:", ps.list_permissions("carol"))
# ['READ', 'ADMIN', 'AUDIT']

# Show raw bitmask for introspection:
print(f"Carol raw bitmask: {ps._get('carol')} = {bin(ps._get('carol'))}")
# Carol raw bitmask: 25 = 0b11001  (bits 0, 3, 4 = READ, ADMIN, AUDIT)

Extension idea: replace the raw integer constants and dictionary with enum.Flag and enum.auto() for production-quality type safety, and add a set_permissions(user_id, permissions) method that replaces the entire bitmask at once.

Quick Reference Cheatsheet

Operator	Name	Operation	Example	Result
`a & b`	AND	1 only where both are 1	`0b1010 & 0b1100`	`0b1000`
`a \| b`	OR	1 where either is 1	`0b1010 \| 0b1100`	`0b1110`
`a ^ b`	XOR	1 where inputs differ	`0b1010 ^ 0b1100`	`0b0110`
`~a`	NOT	Flip all bits	`~5`	`-6`
`a << n`	Left shift	Multiply by 2^n	`3 << 2`	`12`
`a >> n`	Right shift	Floor divide by 2^n	`12 >> 2`	`3`
`n & 1`	Parity check	0=even, 1=odd	`7 & 1`	`1`
`n & (n-1)`	Clear lowest bit	0 iff power of 2	`8 & 7`	`0`
`v \|= flag`	Set bit	Turn bit on	`perms \|= WRITE`	bit set
`v &= ~flag`	Clear bit	Turn bit off	`perms &= ~WRITE`	bit cleared
`v ^= flag`	Toggle bit	Flip bit	`perms ^= WRITE`	bit flipped
`bool(v & flag)`	Test bit	Check if set	`bool(perms & READ)`	`True/False`
`~n == -(n+1)`	Python NOT	Infinite two's complement	`~42`	`-43`
`x ^ x`	XOR identity	Always 0	`n ^ n`	`0`

Key Takeaways

Bitwise operators work on the binary representation of integers at the level of individual bits. They are single CPU instructions and appear throughout operating systems, networking, cryptography, and embedded systems.
Python integers are arbitrary-precision, so there is no overflow and ~n == -(n+1) always - which differs from fixed-width C integers where ~ flips a known number of bits.
The six operators: & (AND, masking/testing), | (OR, setting), ^ (XOR, toggling/differencing), ~ (NOT, complement), << (left shift, multiply by 2^n), >> (right shift, floor divide by 2^n).
The bit flags pattern represents multiple boolean states in one integer: define flags as powers of 2, combine with |, test with & flag, clear with & ~flag, toggle with ^= flag.
Unix file permissions (0o755), socket flags, os.open flags, and most C library constants follow this exact pattern.
XOR has the self-inverse property (x^x==0) enabling the XOR swap and the "find the unique element" O(n) O(1) algorithm.
Always parenthesize when mixing bitwise operators with comparisons. Never use & or | in place of and or or - bitwise operators do not short-circuit.
For production bit flag systems, prefer enum.Flag over raw integers - it gives type safety, readable output, and the same bitwise operator support.
To emulate C's unsigned bitwise NOT in Python, mask with 0xFFFFFFFF (or appropriate width) after ~.

What You Will Learn​

Prerequisites​

Part 1 - Why Bitwise Operators Exist​

Part 2 - Binary Number Representation​

Positional Notation​

Two's Complement and Negative Integers​

Part 3 - The Six Bitwise Operators​

Truth Tables​

Operator 1: & - Bitwise AND (Masking)​

Operator 2: | - Bitwise OR (Setting Bits)​

Operator 3: ^ - Bitwise XOR (Toggling and Differencing)​

Operator 4: ~ - Bitwise NOT (Complement)​

Operator 5: << - Left Shift (Multiply by Powers of 2)​

Operator 6: >> - Right Shift (Arithmetic Divide by Powers of 2)​

Part 4 - The Bit Flags Pattern​

Integers as Sets of Booleans​

Unix File Permissions - The Classic Example​

Part 5 - Engineering Tricks and Algorithms​

Even/Odd Detection Without Division​

Power-of-Two Check​

XOR Tricks​

Fast Multiplication/Division by Powers of 2​

Counting Set Bits (Popcount)​

Part 6 - Python Stdlib and Bitwise Operations​

enum.Flag - Structured Bit Flags​

Socket and OS Flags​

Part 7 - Visualization and Debugging​

Part 8 - Pitfalls and Common Mistakes​

Pitfall 1: ~n Is Not Unsigned NOT​

Pitfall 2: Operator Precedence - & Is Lower Than ==​

Pitfall 3: Large Shifts Are Legal but Expensive​

Pitfall 4: Right-Shifting Does Not Work for Extracting the "Unsigned" High Bits of Negative Numbers​

Interview Questions​

Graded Practice Challenges​

Level 1 - Predict the Output​

Level 2 - Debug the Bug​

Level 3 - Design​

Quick Reference Cheatsheet​

Key Takeaways​

What You Will Learn

Prerequisites

Part 1 - Why Bitwise Operators Exist

Part 2 - Binary Number Representation

Positional Notation

Two's Complement and Negative Integers

Part 3 - The Six Bitwise Operators

Truth Tables

Operator 1: `&` - Bitwise AND (Masking)

Operator 2: `|` - Bitwise OR (Setting Bits)

Operator 3: `^` - Bitwise XOR (Toggling and Differencing)

Operator 4: `~` - Bitwise NOT (Complement)

Operator 5: `<<` - Left Shift (Multiply by Powers of 2)

Operator 6: `>>` - Right Shift (Arithmetic Divide by Powers of 2)

Part 4 - The Bit Flags Pattern

Integers as Sets of Booleans

Unix File Permissions - The Classic Example

Part 5 - Engineering Tricks and Algorithms

Even/Odd Detection Without Division

Power-of-Two Check

XOR Tricks

Fast Multiplication/Division by Powers of 2

Counting Set Bits (Popcount)

Part 6 - Python Stdlib and Bitwise Operations

`enum.Flag` - Structured Bit Flags

Socket and OS Flags

Part 7 - Visualization and Debugging

Part 8 - Pitfalls and Common Mistakes

Pitfall 1: `~n` Is Not Unsigned NOT

Pitfall 2: Operator Precedence - `&` Is Lower Than `==`

Pitfall 3: Large Shifts Are Legal but Expensive

Pitfall 4: Right-Shifting Does Not Work for Extracting the "Unsigned" High Bits of Negative Numbers

Interview Questions

Graded Practice Challenges

Level 1 - Predict the Output

Level 2 - Debug the Bug

Level 3 - Design

Quick Reference Cheatsheet

Key Takeaways