Divisiblity of 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.

Answer 1

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 2

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