Why is ( x & 3 ) identical to ( x mod 4 )?

Unlocking Efficiency: Why (x & 3) is Equivalent to (x % 4)

Explore the fascinating relationship between bitwise AND and the modulo operator, understanding how specific bitwise operations can offer a performance boost for calculating remainders.

In programming, optimizing performance is often a key consideration. While the modulo operator (%) is commonly used to find the remainder of a division, there's a lesser-known trick involving the bitwise AND operator (&) that can achieve the same result under specific conditions, often with greater efficiency. This article delves into why (x & 3) is identical to (x % 4) and how this principle extends to other powers of two.

Understanding Modulo and Bitwise AND

Before we dive into their equivalence, let's briefly review what each operator does:

• Modulo Operator (%): This operator returns the remainder of a division. For example, 10 % 4 equals 2 because 10 divided by 4 is 2 with a remainder of 2.

• Bitwise AND Operator (&): This operator compares two numbers bit by bit. If both bits at the same position are 1, the corresponding result bit is 1; otherwise, it's 0. For example, 10 & 3 involves comparing the binary representations of 10 (1010) and 3 (0011).

flowchart TD
    A[Input Number 'x'] --> B{Is 'x' divided by 'N' (power of 2)?}
    B -- Yes --> C[Modulo: x % N]
    B -- Yes --> D[Bitwise: x & (N-1)]
    C --> E{Result: Remainder}
    D --> E
    E --> F[Output: Remainder]
    style A fill:#f9f,stroke:#333,stroke-width:2px
    style F fill:#bbf,stroke:#333,stroke-width:2px

Conceptual flow of modulo and bitwise AND for powers of two

The Magic of Powers of Two

The equivalence between (x & N-1) and (x % N) holds true when N is a power of two (i.e., 2, 4, 8, 16, etc.). In our specific case, N is 4. Let's look at the binary representations:

• N = 4
• N - 1 = 3

When N is a power of two, N-1 will always be a number consisting of all 1s in its binary representation up to the position just below N. For example:

• 4 in binary is 100
• 3 in binary is 011

When you perform a bitwise AND operation with N-1 (which is 011 for N=4), you are effectively masking the higher-order bits and only retaining the lower-order bits. These lower-order bits represent the remainder when divided by N.

int x = 10;

// Using modulo operator
int remainder_mod = x % 4; // remainder_mod will be 2

// Using bitwise AND operator
int remainder_and = x & 3; // remainder_and will be 2

printf("Modulo result: %d\n", remainder_mod);
printf("Bitwise AND result: %d\n", remainder_and);

C example demonstrating the equivalence for x = 10

Illustrative Examples

Let's break down a few examples to solidify this concept:

Example 1: x = 10

• Binary of 10: 1010
• Binary of 3: 0011
• 1010 & 0011 = 0010 (which is 2 in decimal)
• 10 % 4 = 2

Example 2: x = 7

• Binary of 7: 0111
• Binary of 3: 0011
• 0111 & 0011 = 0011 (which is 3 in decimal)
• 7 % 4 = 3

Example 3: x = 12

• Binary of 12: 1100
• Binary of 3: 0011
• 1100 & 0011 = 0000 (which is 0 in decimal)
• 12 % 4 = 0

In all these cases, the results are identical.

Generalizing the Principle

This principle isn't limited to N=4. It applies to any N that is a power of two. If you need to find x % N where N = 2^k (2 to the power of k), you can use x & (2^k - 1). The (2^k - 1) term effectively creates a bitmask with k trailing ones, isolating the k least significant bits, which represent the remainder.

def modulo_power_of_two(x, n):
    # Check if n is a power of two
    if n > 0 and (n & (n - 1)) == 0:
        return x & (n - 1)
    else:
        # Fallback to standard modulo if n is not a power of two
        return x % n

print(f"10 % 4 = {modulo_power_of_two(10, 4)}") # Output: 2
print(f"15 % 8 = {modulo_power_of_two(15, 8)}") # Output: 7
print(f"20 % 16 = {modulo_power_of_two(20, 16)}") # Output: 4
print(f"10 % 3 = {modulo_power_of_two(10, 3)}") # Output: 1 (uses standard modulo)

Python function demonstrating generalized bitwise modulo for powers of two