Skip to main content
Focus more on choice and implementation of algorithm
Source Link
Simon
  • 141
  • 2

I've improved on @Edward's answer to remove the repeated subraction. This is more true to the algorithm described in that geeksforgeeks link. (YouYou tagged this question "beginner", but that's athat algothithm on geeksforgeeks is fairly advanced algorithm. 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.

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

I've improved on @Edward's answer to remove the repeated subraction. This is more true to the algorithm described in that geeksforgeeks link. (You tagged this question "beginner", but that's a fairly advanced algorithm. Are you sure you should be using it over repeated addition or subtraction?)

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 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));
}
Source Link
Simon
  • 141
  • 2

I've improved on @Edward's answer to remove the repeated subraction. This is more true to the algorithm described in that geeksforgeeks link. (You tagged this question "beginner", but that's a fairly advanced algorithm. Are you sure you should be using it over repeated addition or subtraction?)

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