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

• Is it possible to count and sum digits easily in C? I don't know C, but I do know that a number is divisible by 9 if the sum of its digits is divisible by 9. That little factoid is likely what this problem is hoping you know, given the constraints. The resulting function would be simple then, using recursion; in psuedocode: if (numDigits ==1) then return 9==x; else, return isDivBy9(sumOfDigits(x)); Mar 27, 2015 at 16:35
• @WillemRenzema A number is divisible by 9 iff the sum of its digits in base 10 is divisible by 9, however, the variables are stored in base 2. Converting digits from two bases generally requires division. Mar 27, 2015 at 16:55
• I see no sign that you've designed or tested this program to work with negative numbers. Your question is about numbers, by which I presume you mean integers, not positive integers. Mar 27, 2015 at 16:56
• That is the part that surprises me both in the question and in the answers @EricLippert. Especially given how easy it is to extend ANY algorithm that can determine if positive numbers are divisible by 9. Mar 27, 2015 at 17:00
• Mar 28, 2015 at 13:43

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.

• Why have you tested only positive numbers? Mar 27, 2015 at 16:54
• @EricLippert: simply because that's the domain over which the original function worked, so if it "worked fine" before, I infer that it's the domain of interest. Mar 27, 2015 at 17:36
• Though I see your point, this is a code review site; I assume that the person writing the code hasn't actually read or understood their assignment and they are copying random code off the internet in the hopes that it works. :-) Mar 27, 2015 at 18:25
• @EricLippert: I suppose I'm a little more optimistic about human behavior, so I hope your comments (and the test code I provided) might prompt a little more investigation into such questions as "Is 0 divisible by 9?" and "Is -81 divisible by 9?" Mar 27, 2015 at 18:34
• Unless numbers less than 9 are very likely, it doesn't seem like testing for that every time is really an optimization. Mar 27, 2015 at 20:33

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.

• Excellent work! I have added timing results to my own answer which verifies your relative results and also compares a few others. Mar 28, 2015 at 18:23
• GCC skips the shift, and does the equivalent of return ((uint32_t)x * 0x38e38e39) < 0x1c71c71c;. At this stage, most of the time seems to be the function call overhead (if I declare the function static, it gets inlined and the test program completes in well under a second). Oct 24, 2022 at 9:39

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

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;


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

• Is there any way to avoid while loop in code? Mar 27, 2015 at 14:34
• You are right. I should remove the unwanted code as you have mentioned here. Mar 27, 2015 at 14:35
• @kapil.thakar, not sure how to do that. OK you should, but don't edit the question. Mar 27, 2015 at 14:36
• Sure and Thanks for your valuable suggestion. I want to vote up your answer but I am not able to do it as I don't have 15 points. Mar 27, 2015 at 14:40
• @kapil.thakar OK, Thanks, It's the thought that counts. Have fun coding :) You can also participate in the chat room when you have 20 rep. Mar 27, 2015 at 14:41

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.

• This is by far the best solution so far for the stated problem. I built on your answer to create my own.
– JS1
Mar 28, 2015 at 10:57
• Good answer! Also, since 64 % 9 == 1, we know that 2^(6*n) == 1 for n=0, 1, ... so one could speed things even further by using the same trick for 4096, 262144, 16777216, etc. Mar 28, 2015 at 18:35
• A refinement may be to avoid looping but instead if x>=262144 then run some hard-coded iterations; then if x>=4096, and then if x>=64. Mar 28, 2015 at 22:33
• After the first loop, x is guaranteed to be less than 64 = 8², so (using the fact that 8 ≡ -1 modulo 9) you could replace the last while loop with a simple return (x >> 3) == (x & 7). Mar 29, 2015 at 12:15
• @IlmariKaronen: Good point. If you did that and added x = (x >> 18) + (x & 0x3ffff) at the top, I believe this would run as fast as @JS1s solution for 32 bit numbers. Mar 29, 2015 at 14:21
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.

• Not the most efficient solution either… Mar 27, 2015 at 14:40
• By using addition instead of subtraction, you would see performance improvements. Just start num at 0, then increment by 9 each iteration. Your condition would then be num <= number Mar 27, 2015 at 15:02
• Basically % is slow. And may cause some indecent problems in old C. nevertheless.. it is truly handy. Mar 27, 2015 at 15:08
• "Which one looks easier for reading?" - I think they're equally easy to read. Also, isdivsbl is a terrible suggestion for a name. Mar 27, 2015 at 15:51
• ThisIsPascalCase, thisIsCamelCase - see the difference? Mar 28, 2015 at 14:27

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));
}

• You should primarily review the asker's code. Mar 27, 2015 at 20:32
• I like this algorithm a lot along with Gnasher's. I wonder if it would be faster to eliminate the power of 2 loop. That loop uses a mask, compare, and shift (3 operations total) to process one bit of the input. The main loop uses a compare, shift, subtract, and mask (4 operations) to process 3 bits of the input. So I think you could just get rid of everything before the main loop.
– JS1
Mar 28, 2015 at 8:19
• @Simon I built on your answer to come up with my own. And in doing so, I ran a timing test that showed your main loop is faster by itself without the factors of 2 loop.
– JS1
Mar 28, 2015 at 10:59

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;
}

• And it has to check on each iteration. You have interesting definition for "better". Also I don't know if I am the only one that thinks the C# part is more than irrelevant. Mar 27, 2015 at 15:20
• this code is extendable, it has no magic numbers anywhere in the code.
– Malachi
Mar 27, 2015 at 15:24
• "It has no magic numbers anywhere in the code". Yes it doesn't have 9 despite the fact, everything is about it. Including the name of the function. Also yes it could be extended even more. Say.. debug checking etc. Different level of complexity.. Mar 27, 2015 at 15:26
• It is. Now when I implied mine... the base method. it is more than obvious that it can be improved. The positive arithmetic was also mentioned already. I can't say it isn't better. Please don't take it as a race or something.. because it isn't. Mar 27, 2015 at 15:30
• while ( (i += divisor) < number); Mar 27, 2015 at 15:47

# 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)
{
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)
{
/* A large multiple of 9 */
07777 << (CHAR_BIT * sizeof adjustment - 1 - 12);
while (x < 0) { x += adjustment; } /* max 2 iterations */

while (x >= 010000) {
x = (x & 07777) + (x >> 12);
}

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