Divisiblity by 5 without using % and / operator

Question

How to check whether a number is divisible by 5 or not without using % and / operator?
I want a quickest algorithm for this problem.

I tried subtracting 5 from the number until I get 0 or a negative number. 0 means divisible by 5, negative means not divisible by 5.
But for a big number this will take too much time.

Answer 1

In decimal, a number is divisible by 3 or 9 if the sum of the digits is divisible by 3 or 9

The same applies to any divisors of b - 1 in base b. For example we can sum the digits in base 16 and take modulo 3, 5 or 15 to get the number modulo 3, 5 or 15. See How to find x mod 15 without using any Arithmetic Operations?

In fact we can check divisibility by 5 in any base 2^4k like 16, 256, 4096...

Using that property we have the following solution

unsigned mod5(unsigned x) {
    unsigned mod = 0;
    while (x) {
        mod += x & 0x0F;
        x >>= 4;
    }
    while (mod >= 15)
    {
        if (mod == 15) return 0;
        mod = (mod >> 4) + (mod & 0x0F);
    }
    return mod;   
}

Or it can be further optimized like this using a bit lookup table in the last step

unsigned isDivisibleBy5(unsigned x) {
    x = (x >> 16) + (x & 0xffff);
    x = (x >> 8)  + (x & 0x00ff);
    x = (x >> 4)  + (x & 0x000f);
    return (0x1084210842108421ULL >> x) & 1;
}

Answer 2

It finally got unlocked, so I can explain my comment, which incidentally turns out to generate better code than GCC does for x % 5 == 0. See here, fill in

#include <stdint.h>
bool divisible_by_5(uint32_t x)
{
   return x % 5 == 0;
}
bool divisible_by_5_fast(uint32_t x)
{
   return x * 0xCCCCCCCD <= 0x33333333;
}

I'll assume unsigned input, because the OP suggested an algorithm that only works with positive input. This method can be extended to signed input, but it's a little messy.

0xCCCCCCCD is the modular multiplicative inverse of 5, modulo 2³². Multiplying a multiple of k (for example, n * k) by the (modular) multiplicative inverse is equivalent to dividing by k, because

(n * k) * inv(k) =
// use associativity
n * (k * inv(k)) =
// use definition of multiplicative inverse
n * 1 =
// multiplicative identity
n

Modulo powers of two, a number has a modular multiplicative inverse iff it is odd.

Since multiplying by an odd number is invertible and is actually a bijection, it can't map any non-multiples of k to the 0 - (2³²-1)/k range.

So when it's outside that range, it can't have been a multiple of k.

0x33333333 is (2³²-1)/5, so if x * 0xCCCCCCCD higher, x can't have been a multiple of 5.

Answer 3

bool trythis(int number){
  Int start = number;
  Do{
    start = start - 5;
  } while (start > 5)

  If (start == 5 || start == 0) {
    Return true;
  } else return false;
}

Answer 4

A good starting point is to look into how division can be accomplished with multiplication and bit-shifts. This question is one place to look.

In particular, you can follow the attached post to hit upon the following strategy. First, "divide by 5" using multiplication and bit-shifts:

 int32_t div5(int32_t dividend) {
     int64_t invDivisor = 0x33333333;
     return 1 + (int32_t) ((invDivisor * dividend) >> 32);
 }

Then, take the result and multiply by 5:

int result = div5(dividend) * 5;

Then, result == dividend if and only dividend is divisible by 5.

if(result == dividend) {
    // dividend is divisible by 5
}
else {
    // dividend is not divisible by 5
}

Answer 5

Let's represent the number in base 2. We have:

abcdefgh*101 = ABCDEFGHIJ

or

+abcdefgh00
+  abcdefgh
 ----------
 ABCDEFGHIJ

We are given ABCDEFGHIJ and want to find abcdefgh.

If you alternately - and + ABCDEFGH with its successive rightshift-by-2, you will get...

+  ABCDEFGH
-    ABCDEF
+      ABCD
-        AB
-----------
+  abcdefgh
+    abcdef
-    abcdef
-      abcd
+      abcd
+        ab
-        ab
-----------
   abcdefgh

The answer!

Answer 6

There are two reasons I can see for wanting such an algorithm: (1) homework, or (2) writing efficient code for a microcontroller which does not have efficient division instructions. Assuming your reason is the second, but allowing for the possibility that it might be the first, I won't give you a full solution, but will suggest that if you divide your number into chunks that are a multiple of four bits each, the sum of all those chunks will be divisible by five only if the original number was; note that when performing such computation you must either avoid overflows or else add to your result the number of overflows that have occurred. I don't know any efficient way to do the latter in C, but in many machine languages it is easy. As a simple example, on the 8051 if one had a 32-bit integer, one could so something like:

    mov a,Number   ; Byte 0
    add a,Number+1 ; Byte 1
    adc a,Number+2 ; Byte 2, plus carry from last add
    adc a,Number+3 ; Byte 3, plus carry from last add
    adc a,#0       ; Add in carry, if any (might overflow)
    adc a,#0       ; Add in carry, if any (can't overflow)

Note that in the machine code, adding the carries back into the number is much faster than performing 16-bit math would be.

Once the value has been reduced to the range 0-255, one could add the upper four bits to the lower 4 bits to get a value in the range 0 to 30. One could either test for the seven such values that are multiples of five, or work to reduce the number of possible values further [e.g. if the value is at least 15, subtract 15; if at least 10, subtract 10; if 5, subtract five; if zero, it's a multiple of five].

Answer 7

Keep subtracting by multiples of 5 like 50, 500,100, etc. Start with big numbers. If the result goes in negative then subtract with a smaller number number until you reach 0. Otherwise the number is not divisible.

Answer 8

Add all the bytes and check (by table look-up) if the sum is divisible by 5.

Answer 9

Typecast or convert to a string, then see if the final character is a 5 or 0.