Divide by 9 without using division or multiplication operator

Question

This question I have tried to solve it but couldn't get any way. Any pointers would be appreciated.

Regular subtraction way of doing division is not the intention here, ingenious way of using shifting operator to get this done is the intention.

Answer 1

Although an answer has been accepted, I post mine for what it's worth.

UPDATE. This works by multiplying by a recurring binary fraction. In decimal 1/9 = 0.1111111 recurring. In binary, that is 1/1001 = 0.000111000111000111 recurring.

Notice the binary multiplier is in groups of 6 bits, decimal 7 recurring. So what I want to do here, is to multiply the dividend by 7, shift it right 6 bits, and add it to a running quotient. However to keep significance, I do the shift after the addition, and shift the quotient q after the loop ends to align it properly.

There are up to 6 iterations of the calculation loop for a 32 bit int (6 bits * 6 shifts = 36 bits).

#include<stdio.h>

int main(void)
{
    unsigned x, y, q, d;
    int i, err = 0;

    for (x=1; x<100; x++) {             // candidates
        q = 0;                          // quotient
        y = (x << 3) - x;               // y = x * 7

        while(y) {                      // until nothing significant
            q += y;                     // add (effectively) binary 0.000111
            y >>= 6;                    // realign
        }
        q >>= 6;                        // align

        d  = x / 9;                     // the true answer
        if (d != q) {
            printf ("%d / 9 = %d (%d)\n", x, q, d);     // print any errors
            err++;
        }
    }

    printf ("Errors: %d\n", err);
    return 0;
}

Unfortunately, this fails for every candidate that is a multiple of 9, for rounding error, due to the same reason that multiplying decimal 27 * 0.111111 = 2.999999 and not 3. So I now complicate the answer by keeping the 4 l.s. bits of the quotient for rounding. The result is it works for all int values limited by the two top nibbles, one for the * 7 and one for the * 16 significance.

#include<stdio.h>

int main(void)
{
    unsigned x, y, q, d;
    int i, err = 0;

    for (x=1; x<0x00FFFFFF; x++) {
        q = 8;                          // quotient with (effectively) 0.5 for rounding
        y = (x << 3) - x;               // y = x * 7
        y <<= 4;                        // y *= 16 for rounding

        while(y) {                      // until nothing significant
            q += y;                     // add (effectively) binary 0.000111
            y >>= 6;                    // realign
        }
        q >>= (4 + 6);                  // the 4 bits significance + recurrence

        d  = x / 9;                     // the true answer
        if (d != q) {
            printf ("%d / 9 = %d (%d)\n", x, q, d);     // print any errors
            err++;
        }
    }

    printf ("Errors: %d\n", err);
    return 0;
}

Answer 2

See this answer: https://stackoverflow.com/a/11694778/4907651

Exactly what you're looking for except the divisor is 3.

EDIT: explanation

I will replace the add function with simply + as you're looking for the solution without using * or / only.

In this explanation, we assume we are dividing by 3.

Also, I am assuming you know how to convert decimal to binary and vice versa.

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

This approach uses bitwise operators:

• bitwise AND: &.
• bitwise left shift: <<. Shifts binary values left.
• bitwise right shift: >>. Shifts binary values right.
• bitwise XOR: ^

The first condition (num > 3) is as such because the divisor is 3. In your case, the divisor is 9, so when you use it, the condition must be (num > 9).

Suppose the number we want to divide is 6.

In binary, 6 is represented as 000110.

Now, we enter while (num > 3) loop. The first statement adds sum (initialised to 0) to num >> 2.

What num >> 2 does:

num in binary initially: 00000000 00000110

after bitwise shift: 00000000 00000001 i.e. 1 in decimal

sum after adding num >> 2 is 1.

Since we know num >> 2 is equal to 1, we add that to num & 3.

num in binary initially: 00000000 00000110

3 in binary: 00000000 00000011

For each bit position in the result of expression a & b, the bit is 1 if both operands contain 1, and 0 otherwise

result of num & 3: 00000000 00000010 i.e. 2 in decimal

num after num = (num >> 2) + (num & 3) equals 1 + 2 = 3

Now, since num is EQUAL to 3, we enter if (num==3) loop.

We then add 1 to sum, and return the value. This value of sum is the quotient.

As expected, the value returned is 2.

Hope that wasn't a horrible explanation.

Answer 3

Here's a solution heavily inspired by Hacker's Delight that really uses only bit shifts:

def divu9(n):
    q = n - (n >> 3)
    q = q + (q >> 6)
    q = q + (q>>12) + (q>>24); q = q >> 3
    r = n - (((q << 2) << 1) + q)
    return q + ((r + 7) >> 4)
    #return q + (r > 8)

Answer 4

Create a loop and every step you should substract N-9 .. then (N-9)-9 .. until N<9 OR N=0 and every substraction you count the step For exemple : 36/9 36-9=27 cmpt (1) 27-9=18 cmpt(2) 18-9=9 cmpt(3) 9-9=0 cmpt (4)

So 36/9= 4

Answer 5

This http://en.wikipedia.org/wiki/Ancient_Egyptian_multiplication algorithm can do it using only subtraction and binary shifts in log(n) time. However, as far as I know, state-of-the-art hardware already either use this one, or even better algorithms. Therefore, I do not think there is anything you can do (assuming performance is your goal) unless you can somehow avoid the division completely or change your use case so that you can divide by a power of 2, because there are some tricks for these cases.

Answer 6

If you need to divide a positive number, you can use the following function:

unsigned int divideBy9(unsigned int num) 
{
    unsigned int result = 0;
    while (num >= 9)
    {
        result += 1;
        num -= 9;
    }
    return result;
}

In the case of a negative number, you can use a similar approach.

Hope this helps!

Answer 7

If you're not allowed to multiply/divide, you're left with addition/subtraction. Dividing by a number shows how many times the divisor contains the dividend. You can use this in return: How many times can you subtract the number from the original value?

divisor = 85;
dividend = 9;
remaining = divisor;
result = 0;
while (remaining >= dividend)
{
    remaining -= dividend;
    result++;
}
std::cout << divisor << " / " << dividend << " = " << result;