Bitwise AND OR XOR Operations: Low-Level Algorithm Mastery

1. Introduction and Core Concepts

Bitwise AND, OR, and XOR operations are the fundamental building blocks of low-level computing, operating directly on the binary representation of integers at the level of individual bits. Unlike arithmetic operations that treat numbers as whole quantities, bitwise operations treat each number as a vector of binary digits (0s and 1s) and apply Boolean logic to each corresponding bit position independently. This direct manipulation of bits makes them among the fastest operations a processor can execute, typically completing in a single CPU cycle.

Understanding bitwise and or xor operations is essential for any developer seeking mastery of algorithms, systems programming, and performance optimization. While high-level languages like Python abstract away hardware details, the underlying efficiency of bitwise logic remains critical for tasks ranging from cryptography and compression to embedded systems and competitive programming. These operations provide elegant, constant-time solutions to problems that would otherwise require loops, branching, or additional memory.

At their core, the three primary bitwise operations are defined by simple truth tables applied per bit. AND outputs 1 only if both inputs are 1, OR outputs 1 if at least one input is 1, and XOR (exclusive OR) outputs 1 only if the inputs differ. This per-bit independence is what gives bitwise operations their power and predictability, enabling techniques like masking, toggling, and parity checking without affecting neighboring bits.

The importance of these operations extends far beyond academic exercises. Modern processors contain dedicated Arithmetic Logic Units (ALUs) optimized for bitwise logic, and compilers heavily optimize code that uses them. In Python, integers have arbitrary precision, meaning bitwise operations work seamlessly on numbers of any size, but the conceptual model remains the same: an infinite two's complement representation where operations are performed logically on each bit position.

2. How It Works

To understand how bitwise operations work, you must first visualize numbers in binary. For example, the decimal number 12 is represented as 1100 in binary (8 + 4), and 10 is represented as 1010 (8 + 2). When we compute 12 & 10, 12 | 10, or 12 ^ 10, the processor aligns these binary strings by least significant bit and applies the logical rule column by column, with no carry or borrow between columns unlike addition or subtraction.

Consider the alignment for 12 (1100) and 10 (1010). For AND, the result is 1000 (8), because only the leftmost bit is 1 in both numbers. For OR, the result is 1110 (14), because a 1 appears in either number at the first three positions from the left. For XOR, the result is 0110 (6), because the bits differ in the second and third positions. This column-wise independence is what makes bitwise operations highly parallelizable in hardware.

The Role of Masks and Bit Positions

A central concept in bit manipulation is the mask — a binary pattern used to isolate, set, or clear specific bits. A mask with a single 1 at position k (created by 1 << k) can be used to probe the k-th bit of any number. For instance, to check if the 3rd bit (value 8) is set in a number n, we compute n & (1 << 3). If the result is non-zero, the bit is set. This technique is the foundation for feature flags, permission systems, and hardware register control.

AND is the masking operator: n & mask keeps only the bits where mask has 1s and clears all others to 0. OR is the setting operator: n | mask forces bits to 1 wherever mask has 1s, leaving other bits unchanged. XOR is the toggling operator: n ^ mask flips bits wherever mask has 1s (1 becomes 0, 0 becomes 1) while leaving other bits intact. This toggling property is unique to XOR and is reversible — applying the same XOR mask twice restores the original value: (n ^ mask) ^ mask == n.

Two's Complement and Negative Numbers

In Python and most modern systems, negative numbers are represented using two's complement, an infinite sequence of leading 1s for negative values. This means ~0 equals -1, ~1 equals -2, and so on. While this can be confusing, the bitwise operations themselves remain consistent. For example, -1 in binary is conceptually ...11111111, so -1 & x always equals x, and -1 | x equals -1. Understanding this is crucial when using bitwise NOT (~) or right shifts (>>) on negative numbers, as Python's arithmetic right shift preserves the sign bit.

Another key mechanism is the shift operations, which are intimately related to AND/OR/XOR. Left shift (n << k) multiplies by 2^k by appending k zeros, while right shift (n >> k) divides by 2^k. These are often combined with AND/OR/XOR to extract bit fields, pack multiple values into a single integer, or implement fast multiplication and division by powers of two without using the slower arithmetic operators.

3. Implementation

Python provides native operators for all bitwise operations: & for AND, | for OR, ^ for XOR, ~ for NOT, << for left shift, and >> for right shift. Because Python integers are arbitrary-precision, you do not need to worry about overflow as you would in C or Java, but you must be mindful of the infinite two's complement representation when using ~ and >> on negative numbers. The following implementations demonstrate idiomatic and well-commented usage.

The first example covers the fundamental operations and how to inspect results in binary format. Python's bin() function is invaluable for debugging bitwise code, as it displays the binary string representation. Note that bin() for negative numbers includes a minus sign rather than showing two's complement, so we often mask with 0xFF or 0xFFFF to view a fixed-width representation.

# Basic bitwise AND, OR, XOR demonstration
def demonstrate_basic_ops(a: int, b: int) -> None:
    # AND: keeps only overlapping 1 bits
    and_result = a & b
    # OR: combines 1 bits from either operand
    or_result = a | b
    # XOR: keeps bits where operands differ
    xor_result = a ^ b
    # NOT: inverts all bits (Python uses infinite two's complement)
    not_a = ~a

    print(f"a = {a} ({bin(a)})")
    print(f"b = {b} ({bin(b)})")
    print(f"a & b = {and_result} ({bin(and_result)})  # AND")
    print(f"a | b = {or_result} ({bin(or_result)})  # OR")
    print(f"a ^ b = {xor_result} ({bin(xor_result)})  # XOR")
    print(f"~a = {not_a} ({bin(not_a & 0xFF)} masked to 8 bits)")

# Example: 12 = 0b1100, 10 = 0b1010
demonstrate_basic_ops(12, 10)
# Expected: 12 & 10 = 8 (0b1000), 12 | 10 = 14 (0b1110), 12 ^ 10 = 6 (0b0110)

The second set of utilities shows the most common practical patterns: checking, setting, clearing, and toggling individual bits. These four operations form the basis for nearly all flag and bitmask manipulation in real systems. Each function uses a mask created by shifting 1 to the target position, ensuring only the desired bit is affected.

def bit_utilities(n: int, k: int) -> dict:
    """
    Common bit manipulation utilities for position k (0-indexed from LSB).
    All operations use a mask = 1 << k
    """
    mask = 1 << k

    # 1. Check if k-th bit is set: AND with mask
    is_set = (n & mask) != 0

    # 2. Set k-th bit to 1: OR with mask
    set_bit = n | mask

    # 3. Clear k-th bit to 0: AND with inverted mask
    # ~mask has 0 at position k and 1 elsewhere
    clear_bit = n & ~mask

    # 4. Toggle k-th bit: XOR with mask
    toggle_bit = n ^ mask

    # 5. Extract lowest set bit: n & -n (two's complement trick)
    lowest_set_bit = n & -n

    # 6. Clear lowest set bit: n & (n - 1)
    clear_lowest = n & (n - 1)

    return {
        "is_set": is_set,
        "set_bit": bin(set_bit),
        "clear_bit": bin(clear_bit),
        "toggle_bit": bin(toggle_bit),
        "lowest_set_bit": bin(lowest_set_bit),
        "clear_lowest": bin(clear_lowest)
    }

# Check bit 1 (value 2) in number 10 (0b1010)
print(bit_utilities(10, 1))
# Check bit 2 (value 4) in number 10
print(bit_utilities(10, 2))

A third implementation pattern involves using XOR for reversible operations and efficient swaps. The XOR swap algorithm, while mainly of historical interest due to modern compiler optimizations, perfectly illustrates the algebraic properties of XOR: it is associative, commutative, and self-inverse (a ^ a == 0 and a ^ 0 == a). These properties are exploited in more advanced algorithms like finding a single non-duplicate number in an array.

def xor_swap(a: int, b: int) -> tuple:
    """Swap two integers without temporary variable using XOR."""
    print(f"Before: a={a} ({bin(a)}), b={b} ({bin(b)})")
    # Step 1: a holds a ^ b
    a = a ^ b
    # Step 2: b becomes (a ^ b) ^ b = a
    b = a ^ b
    # Step 3: a becomes (a ^ b) ^ a = b (original b)
    a = a ^ b
    print(f"After: a={a} ({bin(a)}), b={b} ({bin(b)})")
    return a, b

def find_single_number(nums: list) -> int:
    """
    Find the single number that appears once where every other
    number appears exactly twice. Uses XOR cancellation: a ^ a = 0.
    Time O(n), Space O(1).
    """
    result = 0
    for num in nums:
        # XOR accumulates; pairs cancel to 0, single remains
        result ^= num
    return result

xor_swap(12, 10)
print(find_single_number([4, 1, 2, 1, 2]))  # Returns 4

Finally, efficient bit counting and permission flag management demonstrate how AND/OR/XOR combine in systems code. Counting set bits (population count) and managing Unix-style permissions are canonical examples where bitwise operations provide both clarity and performance over arithmetic alternatives.

def count_set_bits_kernighan(n: int) -> int:
    """Count 1 bits using Brian Kernighan's algorithm: n & (n-1) clears lowest set bit."""
    count = 0
    while n > 0:
        # This operation clears the lowest set bit in each iteration
        n = n & (n - 1)
        count += 1
    return count

# Permission flags example using OR to combine and AND to check
READ = 1 << 2   # 0b100 = 4
WRITE = 1 << 1  # 0b010 = 2
EXECUTE = 1 << 0 # 0b001 = 1

def permission_demo():
    # Combine permissions with OR
    user_perm = READ | WRITE  # 0b110 = 6
    # Check permission with AND
    can_read = (user_perm & READ) != 0   # True
    can_execute = (user_perm & EXECUTE) != 0  # False
    # Add permission with OR
    user_perm = user_perm | EXECUTE  # Now 0b111 = 7
    # Remove permission with AND + NOT
    user_perm = user_perm & ~WRITE   # Remove write: 0b101 = 5
    # Toggle permission with XOR
    user_perm = user_perm ^ READ     # Toggle read: 0b001 = 1
    return user_perm, can_read, can_execute

print(count_set_bits_kernighan(13))  # 13 = 0b1101 -> 3 bits set
print(permission_demo())

4. Step-by-Step Example

Let us walk through a complete, concrete example that uses all three operations to solve a classic problem: determining if two numbers have opposite signs, checking for power-of-two, and finding the missing number trick. We will trace the binary values step by step for numbers 12 (1100) and 10 (1010), and then apply the techniques to a larger algorithmic example.

First, consider the task of checking whether two integers have opposite signs without using comparison operators. The sign bit is the most significant bit (1 for negative, 0 for positive in two's complement). XOR of the sign bits will be 1 only if the signs differ. By computing (a ^ b) < 0, we can determine opposite signs because a negative XOR result implies the sign bit is 1. For example, a = 5 (0101) and b = -8 (1011 in 4-bit two's complement), a ^ b = 1110 which is negative, indicating opposite signs.

Next, let us trace the power-of-two check, which relies on AND. A power of two in binary has exactly one 1 bit: 1 (0001), 2 (0010), 4 (0100), 8 (1000). For any such number n, n - 1 flips all bits after and including the single 1: 8 (1000) minus 1 = 7 (0111). Therefore, n & (n - 1) will be 0 only for powers of two (and zero). Tracing n = 8: 1000 & 0111 = 0000 → true. For n = 10: 1010 & 1001 = 1000 → non-zero → false. This is an O(1) check that avoids loops or logarithms.

Walkthrough: Finding the Unique Number with XOR

Consider the array [2, 3, 5, 4, 5, 3, 4] where every number except 2 appears twice. We initialize result = 0 (0000) and XOR each element sequentially. Step 1: result = 0 ^ 2 = 0010. Step 2: result = 0010 ^ 3 (0011) = 0001. Step 3: result = 0001 ^ 5 (0101) = 0100. Step 4: result = 0100 ^ 4 (0100) = 0000. Step 5: result = 0000 ^ 5 (0101) = 0101. Step 6: result = 0101 ^ 3 (0011) = 0110. Step 7: result = 0110 ^ 4 (0100) = 0010 which is 2, the unique number. Pairs cancel because a ^ a = 0, and 0 ^ a = a, so the order does not matter.

This walkthrough highlights why XOR is ideal for parity and difference detection. AND would not work because it would lose information (pair AND does not cancel), and OR would accumulate bits (pair OR remains 1). Only XOR has the self-inverse property that makes cancellation possible. The same principle extends to finding two unique numbers, detecting a missing number in 1..n, and implementing simple checksums where the XOR of all data blocks provides an error-detection code.

Finally, consider a masking example: extracting the lower 4 bits from a byte. Suppose we have value 0b11010110 (214) and want the lower nibble (0110 = 6). We AND with mask 0b00001111 (15): 11010110 & 00001111 = 00000110. To set the upper nibble to 1010 while preserving the lower nibble, we would first clear the upper nibble with AND (~0xF0) then OR with 0xA0: (value & 0x0F) | 0xA0. These two-step clear-then-set patterns are ubiquitous in embedded programming for configuring hardware registers without disturbing unrelated bits.

5. Complexity Analysis

Bitwise AND, OR, and XOR operations are among the most efficient operations available on modern hardware. At the CPU level, they are typically executed in a single clock cycle within the Arithmetic Logic Unit, with throughput of multiple operations per cycle on superscalar processors. This makes their time complexity effectively O(1) for fixed-width integers (32-bit or 64-bit) as used in languages like C, Java, and Go.

In Python, the situation is slightly more nuanced because integers have arbitrary precision. Python's long integer implementation stores numbers as arrays of 30-bit digits (on 64-bit builds). A bitwise operation must iterate over these digits, so the time complexity is O(n) where n is the number of machine words needed to represent the integer, which is proportional to the number of bits. However, for numbers that fit within 30-60 bits (which covers most practical use cases including 32-bit and 64-bit values), this is still effectively constant time. For cryptographic applications with 2048-bit integers, the linear factor becomes measurable but remains highly efficient compared to multiplication or division.

Space complexity is O(1) auxiliary space for the operation itself, as it produces a new integer of similar size to the inputs without requiring additional data structures. The result may require at most max(len(a), len(b)) digits, so the output space is O(n) in the size of the inputs, but no extra temporary space beyond the result is needed. This contrasts with algorithms that require auxiliary arrays or recursion stacks.

When bitwise operations are used within loops, the overall complexity is determined by the loop structure. For example, iterating over an array of n numbers and XORing them together is O(n) time, which is optimal since every element must be examined. Similarly, Brian Kernighan's algorithm for counting set bits runs in O(k) where k is the number of set bits, which is optimal for sparse numbers (few 1s) and degrades to O(w) for dense numbers where w is the word size. This adaptive behavior is why Kernighan's method is preferred over the naive O(w) shift-and-check approach when the number of set bits is expected to be small.

From a practical performance standpoint, bitwise operations also benefit from excellent cache and branch prediction behavior. They involve no branching, no memory indirection, and no floating-point unit usage, making them ideal for tight inner loops, real-time systems, and high-frequency trading platforms where predictable latency is crucial. Benchmarks consistently show bitwise operations are 3-10x faster than equivalent arithmetic or lookup-table approaches for tasks like flag checking or parity computation.

6. Variations and Optimizations

Beyond the basic AND, OR, and XOR, several advanced variations and optimizations leverage their properties for significant performance gains. One of the most important is the use of combined operations to achieve complex bit manipulations in fewer steps. For example, the expression n & (n - 1) clears the lowest set bit, n & -n isolates it, and n | (n - 1) sets all bits below the lowest set bit. These idioms are heavily used in Fenwick Trees (Binary Indexed Trees), combinatorial generation, and memory allocators.

Another powerful optimization is bit packing and bit fields, where multiple small values are packed into a single integer using shifts and OR, then extracted with AND and shifts. For instance, an RGB color can be packed as (r << 16) | (g << 8) | b, storing three 8-bit values in one 32-bit integer. This reduces memory footprint and improves cache locality, which is critical in graphics processing, network packet headers, and database storage engines. The trade-off is slightly more complex access code, but the memory and speed benefits often outweigh this cost.

Common Optimized Idioms

Several idioms have become standard due to their elegance and efficiency. To check if n is a power of two: (n & (n - 1)) == 0 and n != 0. To check if n is even or odd: (n & 1) == 0 for even, which is faster than n % 2 == 0 because it avoids division. To compute the absolute value without branching (in fixed-width languages): (n ^ (n >> 31)) - (n >> 31) for 32-bit integers, though Python's conditional is preferred for readability. To swap bits or reverse bits, a series of XOR and AND with masks can achieve parallel bit reversal in O(log w) steps.

For counting set bits, modern CPUs provide a dedicated POPCNT instruction, which Python 3.8+ exposes via int.bit_count() (or bit_length for related operations). This is implemented in hardware and is significantly faster than any software loop, running in constant time. Similarly, for finding the position of the lowest or highest set bit, Python's int.bit_length() and (n & -n).bit_length() provide O(1) solutions that previously required loops. When targeting CPython, using these built-ins is always preferable to manual implementations for both speed and correctness.

XOR Variations: From Checksums to Ciphers

XOR has unique variations due to its reversibility. XOR linked lists store the XOR of previous and next pointers in a single field, halving memory usage for doubly linked lists at the cost of more complex traversal. XOR ciphers, while not cryptographically secure alone, form the basis for one-time pads (the only theoretically unbreakable cipher when the key is truly random and used once) and are a component of stream ciphers like RC4 and ChaCha20. In RAID storage, XOR parity allows reconstruction of a failed disk: the parity block is the XOR of all data blocks, so any single missing block can be recovered by XORing the remaining blocks with the parity.

Another optimization is using XOR to avoid branching in conditional logic. For example, to conditionally toggle bits without an if statement: n ^ ((-condition) & mask) where condition is 0 or 1. When condition is 1, -condition is all 1s (in two's complement), so the mask is applied; when 0, it is not. This branchless technique is valuable in cryptographic code where timing attacks must be avoided, and in GPU shaders where branching is expensive. Similarly, AND and OR can be used to implement branchless min/max and clamping operations.

7. Real-World Applications

Bitwise operations are pervasive in real-world systems, often hidden beneath abstraction layers but critical for performance and correctness. In web servers and network stacks, they are used extensively for IP address manipulation, subnet masking, and protocol flag handling. An IPv4 address is a 32-bit integer where AND with a subnet mask (e.g., 255.255.255.0 = 0xFFFFFF00) extracts the network portion, and OR with the host portion constructs addresses. Load balancers use consistent hashing with XOR and bit mixing to distribute requests uniformly while minimizing remapping when servers are added or removed.

In databases, bitmap indexes use bit vectors where each bit represents the presence of a value in a row. Queries with AND, OR, and XOR on these bitmaps can be executed using extremely fast bitwise operations on entire words (64 bits at a time), providing orders-of-magnitude speedups for analytical queries over traditional B-tree indexes when cardinality is low. PostgreSQL, Oracle, and ClickHouse all employ bitmap operations for query execution. Similarly, Bloom filters — probabilistic data structures used to test set membership — rely on multiple hash functions setting bits via OR, and checking via AND, to provide O(1) membership tests with minimal memory, used in CDNs and distributed caches to avoid expensive disk lookups.

Operating systems and embedded systems use bitwise operations for permission and flag management. Unix file permissions (rwxrwxrwx) are three groups of three bits, stored as an octal number where READ=4 (100), WRITE=2 (010), EXECUTE=1 (001). Checking permissions is a single AND operation: if (mode & 0o400) != 0 then owner can read. Device drivers manipulate hardware registers where each bit controls a physical feature — setting a bit via OR enables an interrupt, clearing via AND disables it, toggling via XOR flips a state. This direct hardware control would be impossible without bitwise logic, and the efficiency is critical when handling thousands of interrupts per second.

In cryptography and security, XOR is fundamental. Every modern block cipher (AES) and stream cipher uses XOR to combine plaintext with key material, as XOR is the only operation that is both its own inverse and preserves entropy. Hash functions use a mix of AND, OR, XOR, and rotations to achieve avalanche effects where flipping one input bit changes half the output bits. Checksums and CRCs (Cyclic Redundancy Checks) used in Ethernet, ZIP files, and Git all rely on polynomial division implemented via XOR and shifts to detect transmission errors. Even high-level applications like feature flag systems in web applications often store user entitlements as bitmasks — a single 64-bit integer can represent 64 boolean features, checked with a single AND instead of 64 separate boolean fields, reducing database storage and improving cache efficiency.

Graphics and game development provide another rich domain. Alpha blending, collision detection with bitmasks, and sprite manipulation all use bitwise operations for speed. In chess engines, bitboards represent the board as 64-bit integers where each bit is a square; move generation becomes a series of shifts, ANDs, and ORs that can evaluate millions of positions per second. Compression algorithms like Huffman coding, LZ77, and run-length encoding pack variable-length codes using shifts and OR, and decompress using AND and shifts to extract codes, achieving significant storage savings for text, images, and video.

8. Comparison with Alternatives

While bitwise operations are optimal for many low-level tasks, they are not always the best choice compared to higher-level alternatives. The decision depends on readability, portability, domain requirements, and whether the problem is inherently bit-oriented. For example, using arithmetic (n % 2) to check even/odd is more readable for beginners than (n & 1), though the latter is faster. Similarly, using Python sets to find a unique number is more intuitive than XOR, but uses O(n) extra space versus O(1) for XOR. Understanding these trade-offs is key to writing maintainable yet performant code.

For flag management, the alternative to bitmasks is using dictionaries, sets, or boolean fields. Bitmasks are more memory-efficient and faster for checking multiple flags simultaneously (single AND vs multiple lookups), but they are limited to a fixed number of flags (64 for a 64-bit integer) and are less self-documenting. For permission systems with dozens of flags, an Enum Flag in Python provides a good balance, offering named constants with bitwise semantics. For larger or dynamic flag sets, a set of strings may be more appropriate despite the overhead.

In terms of arithmetic, shifts can replace multiplication/division by powers of two, but modern compilers already optimize n * 8 to n << 3 automatically, so manual replacement often harms readability without benefit. However, in performance-critical loops or when the shift amount is variable, explicit shifts can still be advantageous. For exponentiation, bitwise operations enable fast exponentiation by squaring, which is O(log n) versus O(n) for naive multiplication, but Python's built-in pow(base, exp, mod) already implements this efficiently in C, so it should be preferred.

The table illustrates that bitwise operations excel when the problem is inherently about bits, flags, or compact representation. For general application logic, higher-level abstractions are often preferable for maintainability. A common anti-pattern is over-optimizing with bitwise tricks where clarity matters more than nanoseconds — for example, using n >> 1 instead of n // 2 in business logic. The best practice is to use bitwise operations where they provide clear algorithmic advantages (like XOR cancellation or bitmap indexes) and to encapsulate them behind well-named functions or constants so that callers do not need to understand the bit-level details.

Another alternative is using specialized libraries or hardware instructions. For population count, Python's int.bit_count() (Python 3.8+) or numpy's bitwise functions are faster than manual loops. For cryptography, never implement XOR ciphers manually; use the cryptography library which handles constant-time operations and side-channel resistance. For large bitmaps, libraries like python-bitarray or Roaring Bitmaps provide compressed, optimized implementations that outperform naive Python integers for sparse data. Choosing the right abstraction level — raw bitwise ops, standard library, or specialized library — depends on performance requirements and correctness guarantees needed.

9. Common Mistakes and Best Practices

Despite their simplicity, bitwise operations are a frequent source of bugs, especially for developers unfamiliar with operator precedence, sign extension, and Python's arbitrary-precision semantics. One of the most common mistakes is confusing bitwise operators (&, |, ^) with logical operators (and, or). In Python, 2 & 3 evaluates to 2 (10 & 11 = 10), while 2 and 3 evaluates to 3 due to truthiness and short-circuiting. This error is particularly insidious in conditions: if a & b == 0 is parsed as a & (b == 0) due to precedence, not (a & b) == 0. Always parenthesize bitwise expressions in conditions.

Operator precedence is a major pitfall. In Python, comparison operators (==, !=, <, >) have higher precedence than bitwise operators, so x & 1 == 0 is equivalent to x & (1 == 0) which is x & False which is 0, always falsy. The correct form is (x & 1) == 0. Similarly, shifts have higher precedence than AND/OR, so x >> 1 & mask is (x >> 1) & mask, which is usually intended, but explicit parentheses improve clarity. A best practice is to always parenthesize any expression mixing bitwise, comparison, or arithmetic operators, even when not strictly necessary, to make intent explicit and avoid subtle bugs that pass code review.

Another frequent mistake involves the bitwise NOT operator (~) and infinite precision. In C, ~0 is -1 for 32-bit ints, but also 0xFFFFFFFF if treated as unsigned. In Python, ~0 is -1, ~1 is -2, and ~0xFF is -256, not 0x00. Developers expecting a fixed-width complement are surprised when ~0b00001111 yields -16 instead of 0b11110000. To get a fixed-width NOT, mask the result: (~n) & 0xFF for 8 bits, (~n) & 0xFFFF for 16 bits. Similarly, right shift (>>) on negative numbers performs arithmetic shift (sign extension), so -8 >> 1 is -4, not a large positive number. If logical shift (zero fill) is needed, mask after shifting or use unsigned semantics via & ((1 << width) - 1).

Best practices include using named constants and enums for masks instead of magic numbers. Instead of if perm & 0b100, define READ = 1 << 2 and write if perm & READ, which is self-documenting and less error-prone. Use Python's enum.Flag for type-safe flag combinations. Document the bit layout with comments or diagrams, especially when packing multiple fields: # bits 0-7: lower, 8-15: upper. Write helper functions for common operations (is_set, set_bit, clear_bit) rather than inlining bitwise expressions throughout the codebase, which centralizes logic and simplifies testing. Finally, prefer Python's built-ins like int.bit_count(), int.bit_length(), and bitarray where appropriate, as they are implemented in C, handle edge cases correctly, and are more readable than manual bit twiddling. Always test bitwise code with edge cases: 0, -1, maximum values, and numbers with all bits set or cleared, as these often expose off-by-one and sign errors.

10. Interview Questions

Bitwise operations are a staple of technical interviews because they test understanding of binary representation, algorithmic optimization, and the ability to find elegant constant-space solutions. Interviewers often expect candidates to move beyond brute force and recognize when AND/OR/XOR provide O(1) space or O(n) time improvements. Below are common questions with the expected approach and key insights.

Question 1: Find the single number that appears once where every other number appears twice. Given an array like [2,2,1], return 1. The optimal solution uses XOR cancellation. As shown earlier, XORing all numbers cancels pairs (a ^ a = 0) and leaves the single number (0 ^ a = a). The solution is a single loop with result ^= num, O(n) time and O(1) space. Follow-up: What if every number appears three times except one? This requires counting bits modulo 3 using AND/OR or using a state machine with two variables (ones, twos) and is a harder variation that tests deeper bit manipulation.

Question 2: Determine if a number is a power of two without loops or recursion. The expected answer is return n > 0 and (n & (n - 1)) == 0. Candidates should explain why: powers of two have one set bit, and n - 1 flips all lower bits, so AND is zero. Common mistakes include forgetting to handle n <= 0 (0 and negatives are not powers of two) and using logarithms which introduce floating-point errors. An alternative follow-up is to count set bits or check if n is a power of four, which adds the condition (n & 0x55555555) != 0 to ensure the single 1 is in an even position.

Question 3: Swap two numbers without a temporary variable, and count the number of set bits. For swapping, the XOR swap (a ^= b; b ^= a; a ^= b) is the classic answer, though candidates should mention that in Python, a, b = b, a is more idiomatic and that XOR swap fails if a and b refer to the same memory location (a ^ a = 0). For counting set bits, the naive loop checking (n >> i) & 1 is O(w), while Brian Kernighan's n & (n - 1) loop is O(k) where k is set bits, and Python's n.bit_count() is optimal. Interviewers look for the ability to discuss trade-offs and to handle negative numbers correctly.

Question 4: Given two integers, find the number of bits that need to be flipped to convert one to the other (Hamming distance). The solution is to compute xor = a ^ b, which has 1s exactly where bits differ, then count set bits in xor. This combines XOR for difference detection and population count. For example, a=10 (1010), b=12 (1100), xor=0110 (6) which has two 1s, so two flips needed. Candidates should implement count via Kernighan or bit_count and discuss O(1) vs O(w) counting. A follow-up is to find the Hamming distance for an array of numbers or to handle 32-bit vs 64-bit widths.

Question 5: Reverse bits of a 32-bit unsigned integer. For example, 0b00000010100101000001111010011100 reversed is 0b00111001011110000010100101000000. The brute force shifts bits one by one in O(w) time, but an optimized divide-and-conquer approach uses masks and shifts in parallel: swap 16-bit halves, then 8-bit, 4-bit, 2-bit, and 1-bit chunks using AND with masks like 0xFF00FF00 and shifts. This runs in O(log w) steps and demonstrates mastery of masking and shifting. In Python, candidates must mask to 32 bits after operations to simulate fixed width: (n & 0xFFFFFFFF). This question tests precision with masks and understanding of bit-level parallelism.