Checking if a number is divisible by 9

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.

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 
#include 

int isDivby9(int x)
{
    while (0 == (x & 1)) {
        x >>= 1;
    }
    if(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 

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.

StackExchange Code Review Q#85163, answer score: 44