Checking if a number is divisible by 9

Question

I tried to develop a new way to check if a number is divisible by 9. I have written my code and it is working fine. I'm not allowed to use *,/ and %.

int isDivby9(int x)
{
    int status = 0; 
    int divby8 = 0;

        int orgx = x;
        if(x>=9)
        {
            divby8 = x >> 3;
            int olddivby8 = divby8;
            while(divby8 >= 9)
            {
                divby8 = divby8 - 9;
            }
            if(divby8 == (orgx - (olddivby8 << 3)))
            {
                status = 1;
            }
            else{
                status = 0;
            }
            x = divby8;
        }

    return status;
}

Can someone please check if this is a good way to check if a number is divisibility by 9? Is it too complex? Is there any better way to perform the same? I also referred to the logic given in geeksforgeeks.

Answer 1

I see some things that you might want to use to improve your code.

Use an early bailout

If the passed number x is less than 9, the routine can immediately return 0.

Eliminate multiples of 2

Since 9 and 2 have no common factors, you can speed up the operation (on average) by shifting the incoming x to the right until the least significant bit is non-zero.

Eliminate unused variables

With a minor restructuring of the code, you can eliminate most of the variables and make the code shorter, faster and easier to read.

Consider implementing a test program

You have apparently already done some testing, but posting the test with the code to be reviewed may help others review the code properly.

Putting it all together

Here's what I came up with using all of these suggestions:

#include <stdio.h>
#include <assert.h>

int isDivby9(int x)
{
    while (0 == (x & 1)) {
        x >>= 1;
    }
    if(x<9)
        return 0;

    int divby8 = x >> 3;
    while(divby8 >= 9) {
        divby8 -= 9;
    }
    return divby8 == (x & 7);
}

int main()
{
    for (int i=1; i < 1000000; ++i) 
        assert(isDivby9(i) == (i%9 == 0));
}

Results

On my machine (64-bit Linux box), the original code runs in 2.3 seconds, and the version above completes in 1.5 seconds; a considerable improvement in performance with identical mathematical results. By comparison, the straightforward approach in @Edenia's answer takes 18.8 seconds on the same machine.

All were compiled with gcc 4.9.2 with -O2 optimizations.

Updated algorithm

I couldn't stop thinking about this question because I knew there was a better algorithm, but just couldn't think of it. I finally came across this superb answer to a similar question on StackOverflow. With that excellent answer, I translated a finite state machine implemention into C and came up with this:

#include <limits.h>

struct state {
    int nextstate[2];
};
int isDivby9 (int num)
{
    static const int HIGH_BIT = INT_MAX - (INT_MAX >> 1);
    static const struct state states[9] = { 
        {{0, 1}}, {{2, 3}}, {{4, 5}}, 
        {{6, 7}}, {{8, 0}}, {{1, 2}}, 
        {{3, 4}}, {{5, 6}}, {{7, 8}}
    };
    if (num < 0) 
        num = -num;        
    int s = 0;
    for ( ; num ; num <<= 1) {
        s = states[s].nextstate[(num & HIGH_BIT) ? 1 : 0];
    }
    return s==0;
}

Each bit, starting from the MSB, drives the state machine to the next state. The state is held in variable s and the branches for the 0 and 1 bits are the the two nextstate entries. It works well (including for negative numbers and zero) and is very fast. In fact, on my machine, this routine takes 0.045 seconds.

Updated results

In more concise timing tests on my machine, and adjusting all routines to also work correctly on negative numbers, here's what I found on this machine:

  861092 modulus operator
 1152840 JS1
 1581770 gnasher729
 2479987 Simon
 8961866 Edward DFA function

So the % operator is fastest, followed by @JS1's routine, followed by @gnasher729's, followed by @Simon's followed by the DFA routine (by a wide margin!)

Naturally, this might differ on different machines with different architectures, so as always, timing routines on your own actual hardware is recommended.

I learned some things that might well be useful for the next time I work on synthesizing my own logic or on an embedded microprocessor without a multiply instruction.

Answer 2

After reading gnasher729 and Simon's answers, I was inspired to find the fastest possible way to do this.

Analysis of original function

The main problem with the original function is that it only uses the divide by 8 trick once. After that, it falls into this loop:

    while(divby8 >= 9)
    {
        divby8 = divby8 - 9;
    }

Given a large number, this loop could iterate for millions of iterations.

Faster solutions

Gnasher729 and Simon demonstrated solutions that used a small loop to reduce the original number by 6 and 3 bits respectively. Building upon their work, I came up with the following optimized solution:

int div9(int x)
{
    x = (x >> 15) - (x & 0x7fff);
    x = (x >> 9) - (x & 0x1ff);
    x = (x >> 6) + (x & 0x3f);
    x = (x >> 3) - (x & 0x7);
    return x == 0;
}

This function is meant to be used for 32-bit positive integers. For 64-bit positive integers, you can add this line at the beginning:

    x = (x >> 30) + (x & 0x3fffffff);

If negative integers are allowed, you can add this line at the beginning:

    if (x < 0) x = -x;

Just for fun

The original question did not allow multiply or modulo. But just for fun, let's see what would be the fastest method. For example, how fast is simply using modulo?

int div9(int x)
{
    return (x % 9) == 0;
}

Here is the fastest solution I could come up with, using multiply. This solution is based on this stackoverflow answer. The shift by 6 is to get the original number small enough to work with the multiply trick.

int div9(int x)
{
    x = (x >> 6) + (x & 0x3f);
    return (x * 0xe38e38e4u) < 0x1c71c71c;
}

Timing function

Here is the main function of my timing program. It tests all values from 0 to 0x7ffffff4. I chose to do it this way to avoid using i%9 in the test loop, since i%9 can take a significant amount of time compared to the actual functions being tested.

int main(void)
{
    int i;
    for (i=0;i<0x7ffffff5;i+=9) {
        if (div9(i+0) == 0) break;
        if (div9(i+1) == 1) break;
        if (div9(i+2) == 1) break;
        if (div9(i+3) == 1) break;
        if (div9(i+4) == 1) break;
        if (div9(i+5) == 1) break;
        if (div9(i+6) == 1) break;
        if (div9(i+7) == 1) break;
        if (div9(i+8) == 1) break;
    }
    if (i != 0x7ffffff5) {
        printf("Failed on 0x%08x\n", i);
        return 1;
    }
    return 0;
}

Timing results

Author              Time (seconds)
------              --------------
JS1 (multiply)           2.23
JS1 (modulo)             3.35
JS1 (shifts)             5.70
Gnasher729              16.90
Simon (opt)             30.40
Simon                   53.40

Simon (opt) is his function with only the shift by 3 loop. As you can see, it is faster without having the loop that checks for powers of 2.

Answer 3

I did not check if your code works, I assume it does since you say so.

Your code lacks consistency

if(divby8 == (orgx - (olddivby8 << 3)))
{
   //...
}

vs

else{
   //...
}

and

if(x>=9) vs while(divby8 >= 9)

I suggest using an automated formatting tool.

Avoid nesting

You can avoid nesting by inverting the outer if statement and returning 0. Your nesting isn't that deep so it isn't a major problem.

Unneeded code

I don't see any point of having these lines.

else{
    status = 0;
}
x = divby8;

Comments

You should add comments explaining why. Ex: On if(x>=9) you can add

// It cannot be divisible by 9 if it is less than 9 

Answer 4

If the input is large, the code will run for a very, very long time. If you changed the type from int to int64_t, it could run forever.

You could use the fact that 64 % 9 == 1, therefore (64x + y) % 9 == (x + y) % 9.

while (x >= 64) x = (x >> 6) + (x & 0x3f);
while (x >= 9) x -= 9;

Even for the largest x you will have less than 20 loop iterations in total.

Answer 5

int divides9 (int number)
{
    int num;

    for(num = number; num > 0; num -= 9);

    return (num == 0);
}

Facing your restrictions, I could come up with this that appears to be different than your current approach. And smaller indeed.

---

Not only unnecessary, but also very confusing: The names you use are very long. Camel case is not very readable with long names.

• PreferCamelCaseOverSnakeCaseForLongNames

• prefer_snake_case_over_camel_case_for_long_names

Which one looks easier for reading? Right.

So you can replace isDivby9 with is_divisible_by9 or if you want to stick with abbreviated names - isdivsbl and specify the number that has to be check as a function argument.

What is orgx supposed to do? At the time I read it, I could not get any idea.

olddivby8 is even worse. That stands for all the names. Stick with a style and try to come up with a short name that makes perfect sense and is pretty much self-explaining.

---

Use spaces. Especially between declaration and an if statement.

---

Using bit operations for such arithmetic is a rare case, and not always that pretty. Especially if they are not needed. Exactly because it is a rare case you should not use them unless they are your only choice. They are harder for debugging.

Answer 6

You tagged this question "beginner", but that algothithm on geeksforgeeks is fairly advanced. Are you sure you should be using it over the simple repeated addition or subtraction? In fact, you're still doing repeated subtraction by 9 when you do this:

while(divby8 >= 9)
    {
        divby8 = divby8 - 9;
    }

Thus, you're not getting the full benefit of the bitwise algorithm.

I altered @Edward's code (all good suggestions there) to more faithfully implement the algorithm you linked. The performance gain is significant -- timed on my machine at 0.018s for this vs 3.497s for @Edward's and 41.787s for @Edenia's.

#include <stdio.h>
#include <assert.h>

int isDivby9(int x)
{
    // early bailout when x is 0, otherwise the factor of 2 loop does not terminate.
    if (x == 0) {
        return 1;
    }

    // eliminate factors of 2
    while (0 == (x & 1)) {
        x >>= 1;
    }

    // repeatedly reduce the problem to testing whether (floor(x/8) - x%8) is divisible by 9
    // until we can use the trivial case of whether a number smaller than 9 is divisible by 9.
    // Note that x & 7 is not equal to x % 8 for negative numbers,
    // nor is floor(x/8) appropriate for negative numbers.
    // The algorithm requires a truncation toward 0, not to the next lower integer like floor() or >> 3 does.
    while (x >= 9) {
        x = (x >> 3) - (x & 7);
    }

    return x == 0;
}

int main()
{
    for (int i=0; i < 1000000; ++i)
        assert(isDivby9(i) == (i%9 == 0));
}

Answer 7

I really didn't like the way that @Edenia wrote the code; mine is like hers, only I think it is much cleaner and straightforward:

    int isDivisibleBy(int number, int divisor)
    {
        for (int i = 0; i <= number; i += divisor)
        {
            if (i == number)
            {
                return 1;
            }
        }
        return 0;
    }

and this will work for any set of numbers and divisors.

---

The reason I like my code better is because the for loop is complete in a single block; while this may be aesthetic, it still seems cleaner to me. And we add up to the Number so on the final run we see whether or not we land on the number by incrementing of the divisor until we reach the number.

Neither @Edenia's nor my answer will work for Negative numbers, so please be wary of plugging in a negative number in there.

---

Because I was told this was not better than other code, I formulated a while loop version of this code as well; it is as follows and only checks the outcome once, and is still straight forward as to what it is doing.

int isDivisibleBy(int number, int divisor)
{
    int i = 0;
    while (i < number)
    {
        i += divisor;
    }
    return i == number;
}

Answer 8

Include the tests

No tests were provided, so I had to write my own test functions:

#include <stdio.h>
int expect_eq(const char* file, const int line,
              const char* sa, const char *sb,
              int a, int b)
{
    if (a == b) { return 0; }
    fprintf(stderr, "%s:%d: error: %s (=%d) != %s (=%d)\n",
            file, line, sa, a, sb, b);
    return 1;
}
#define EXPECT_EQ(a, b) expect_eq(__FILE__, __LINE__, #a, #b, a, b)

int main(void)
{
    return EXPECT_EQ(isDivby9(0), 1)
        |  EXPECT_EQ(isDivby9(1), 0)
        /* TODO: add more tests */
        ;
}

The very first test I tried failed: isDivby9(0) returned a false value, but 0 is exactly 0✕9. That's a failed review right there.

---

Implement the algorithm as written

The referenced code uses a recursive call of isDivby9(), but this implementation does not. If it's to be a direct implementation, make it true to the source (which we could do by directly copying the C++ function, if we include <stdbool.h> first).

It may be slightly more useful if we divide it into two functions:

#include <stdbool.h>
int mod9(int x)
{
    if (x < 9) { return x; }
    x = (x & 07) - mod9(x >> 3);
    if (x >= 9) x -= 9;          /* range correction for subtraction */
    return x;
}

bool isDivby9(int x)
{
    return mod9(x) == 0;
}

---

Consider a simpler algorithm

We know that to find the residue of a number modulo m, we can express it in base (m+1) and simply add the digits (this is how the well-known check for multiples of 9 works in decimal). If we choose base-64 for our representation, that's convenient for bitwise operations and 63 is a multiple of 9.

Once we have reduced the number modulo 63, then we have two octal digits. The "eights" digit can be subtracted from the units digit (since 8✕n ≡ -1✕n, mod 9).

That gives us a nice iterative algorithm:

int mod9(int x)
{
    /* add base-64 digits */
    while (x >= 0100) {
        x = (x & 077) + (x >> 6);
    }
    /* we now have two octal digits - subtract the eights from the units */
    x = (x & 07) - (x >> 3);
    x += x < 0 ? 9 : x >= 9 ? -9 : 0; /* bring subtraction into range */
    return x;
}

It still gives us incorrect answers for negative values, except on rare platforms where int has a multiple of 6 bits.

---

Handle negative values correctly

This function accepts an int, which has a range of at least [-32767,32767]. But we produce incorrect answers for much of that range.

A simple way to get the right results for negative numbers is to add a large multiple of 9 to make a positive number without changing the result. To create a large multiple of 9, the easiest way is to take a smaller one (no more than the smallest INT_MAX we are guaranteed), and shift it left as far as we are able. Then we should only have to add this value twice at most:

    static const int adjustment =
        /* A large multiple of 9 */
        07777 << (CHAR_BIT * sizeof adjustment - 1 - 12);
    while (x < 0) { x += adjustment; } /* max 2 iterations */

---

Modified code

Applying the above changes, and including the tests that motivate them, we get:

#include <limits.h>
#include <stdbool.h>

int mod9(int x)
{
    static const int adjustment =
        /* A large multiple of 9 */
        07777 << (CHAR_BIT * sizeof adjustment - 1 - 12);
    while (x < 0) { x += adjustment; } /* max 2 iterations */

    /* add base-4096 digits */
    while (x >= 010000) {
        x = (x & 07777) + (x >> 12);
    }

    /* add base-64 digits */
    x = (x & 077) + (x >> 6);
    /* we now have two octal digits, plus possibly one overflow - subtract the eights from the units */
    x = 9 + (x & 07) - (x >> 3); /* adding 9 ensures a positive result */
    x = (x & 07) - (x >> 3);
    return x;
}

bool isDivby9(int x)
{
    return mod9(x) == 0;
}

#include <stdio.h>
int expect_eq(const char* file, const int line,
              const char* sa, const char *sb,
              int a, int b)
{
    if (a == b) { return 0; }
    fprintf(stderr, "%s:%d: error: %s (=%d) != %s (=%d)\n",
            file, line, sa, a, sb, b);
    return 1;
}
#define EXPECT_EQ(a, b) expect_eq(__FILE__, __LINE__, #a, #b, a, b)

int main(void)
{
    return EXPECT_EQ(mod9(0), 0)
        |  EXPECT_EQ(mod9(1), 1)
        |  EXPECT_EQ(mod9(8), 8)
        |  EXPECT_EQ(mod9(9), 0)
        |  EXPECT_EQ(mod9(10), 1)
        |  EXPECT_EQ(mod9(32075), 8)
        |  EXPECT_EQ(mod9(32076), 0)
        |  EXPECT_EQ(mod9(32767), 7)
        |  EXPECT_EQ(mod9(-1), 8)
        |  EXPECT_EQ(mod9(-8), 1)
        |  EXPECT_EQ(mod9(-9), 0)
        |  EXPECT_EQ(mod9(-10), 8)
        |  EXPECT_EQ(mod9(-17), 1)
        |  EXPECT_EQ(mod9(-18), 0)
        |  EXPECT_EQ(mod9(-19), 8)
        |  EXPECT_EQ(mod9(-32075), 1)
        |  EXPECT_EQ(mod9(-32076), 0)
        |  EXPECT_EQ(mod9(-32767), 2)
        ;
}

Performance-wise, this falls roughly halfway between JS1 and Gnasher implementations, at 3¾ times JS1(multiply) on my system. But be aware that JS1 requires a positive 32-bit int, whereas mine is fully portable.

Interestingly, with my compiler, a simple x%9 beats all bitwise implementations presented in answers here - I confirmed that GCC uses a "magic" multiplication internally (and, obviously, tailored to its target architecture, so totally portable at the source-code level).

---

Exercise

Use this technique to test whether a number is a multiple of 11.

Hint: 2⁵ + 1 = 3 ✕ 11