Green goblin Green goblin - 2 months ago 8
C Question

Divide a number by 3 without using *, /, +, -, % operators

How would you divide a number by 3 without using

*
,
/
,
+
,
-
,
%
, operators?

The number may be signed or unsigned.

Answer

This is a simple function which performs the desired operation.But it requires + operator, so all you have to do is to add the values with the bit-operators:

// replaces the + operator
int add(int x, int y) {
    while(x) {
        int t = (x & y) <<1;
        y ^= x;
        x = t;
    }
    return y;
}

int divideby3 (int num) {
    int sum = 0;
    while (num > 3) {
        sum = add(num >> 2, sum);
        num = add(num >> 2, num & 3);
    }
    if (num == 3)
        sum = add(sum, 1);
    return sum; 
}

As Jim commented this works because:

  • n = 4 * a + b
  • n / 3 = a + (a + b) / 3
  • So sum += a, n = a + b, and iterate

  • When a == 0 (n < 4), sum += floor(n / 3); i.e. 1, if n == 3, else 0

Comments