C Program to implement modulo (%) operator using bitwise operators

This is a common interview question to implement the modulo operator without using the operator itself. Here we will solve the problem using a C program.

C Program

#include <stdio.h>
#include <stdint.h>

// Function to compute a % b using bitwise operators
int bitwise_mod_signed(int a, int b)
{
    if (b == 0) {
        printf("Error: Division by zero\n");
        return 0;
    }

    // Work with absolute values
    unsigned int dividend = (a < 0) ? -a : a;
    unsigned int divisor  = (b < 0) ? -b : b;

    unsigned int remainder = dividend;
    unsigned int shifted_divisor = divisor;

    int shift = 0;
    // Find the largest power of 2 multiple of divisor <= dividend
    while (((shifted_divisor << 1) <= remainder) && (shifted_divisor << 1)) {
        shifted_divisor <<= 1;
        shift++;
    }

    // Perform division via repeated subtraction with shifting
    while (shift >= 0) {
        if (remainder >= shifted_divisor) {
            remainder -= shifted_divisor;
    }
        shifted_divisor >>= 1;
        shift--;
    }

    // Apply sign rule: remainder has the sign of dividend
    return (a < 0) ? -(int)remainder : (int)remainder;
}

int main()
{
    int a, b;

    printf("Enter dividend (a): ");
    scanf("%d", &a);
    printf("Enter divisor (b): ");
    scanf("%d", &b);

    int result = bitwise_mod_signed(a, b);

    printf("%d %% %d = %d\n", a, b, result);

    return 0;
}

Code Walkthrough

We are trying to implement % (modulo) without using / or %. Instead, we only use bitwise operators (<<, >>, &, |) and subtraction.

1. What does % mean?

If you divide a by b then % gives you the remainder.

Example:

29 / 5 = 5 remainder 4
So, 29 % 5 = 4

2. Problem: we can’t use / or %

So how do we get the remainder? We use a trick called binary long division, but with bitwise shifting.

3. How it works step by step

Step A: Work with positive numbers first

If a = -29 and b = 5, we first take absolute values:

|-29| = 29, |5| = 5

We’ll fix the sign at the end.

Step B: Line up divisor with dividend

We want to find the biggest multiple of b that fits inside a. But instead of multiplying, we shift bits.

Example:

29 (a) = 11101 (binary)
5  (b) = 00101 (binary)

Shift 5 left until it’s just below 29:

5 << 2 = 20 (binary 10100)   ✅ fits in 29
5 << 3 = 40 (binary 101000)  ❌ too big

So the biggest shifted divisor we can use is 20.

Step C: Subtract repeatedly

Now subtract:

29 - 20 = 9

Then shift divisor back (10, then 5) and subtract again if possible:

9 - 5 = 4

Now 4 is smaller than divisor (5), so we stop.

👉 The leftover (4) is the remainder.

Step D: Apply the sign rule

In C, the remainder takes the same sign as the dividend (a).

If a is positive → remainder stays positive.

If a is negative → remainder becomes negative.

Examples:

29 % 5  = 4
-29 % 5 = -4
29 % -5 = 4
-29 % -5 = -4

4. Why shifting works?

Shifting left (<<) is like multiplying by 2.
Shifting right (>>) is like dividing by 2.

So instead of trying every multiple of b, we “line it up” quickly by shifting until it almost reaches a, then subtract step by step.

✅ This way, we can compute % without ever using / or %.