Saturday, January 7, 2012

Compute if a number is a multiple of 5

You can use just bit operations

2 comments:

  1. Here the first five multiple of 5:

    00101
    01010
    01111
    10100
    11001
    ...

    So, It seems that the pattern is: C = A XOR B i.e. the number in position C is the result of the XOR between the previous two numbers (of course the first two numbers of the sequence - 5 and 10 - are given).

    So, an algo could be to generate the sequence of all the possible binary numbers using the previous pattern until we reach the input number (so it is a multiplo of 5). As soon as we generate a bigger number we stops saying that the number is not a multiple of 5.

    ReplyDelete
  2. The above logic fails. 20 is not from 10 XOR 15.

    It is matter of checking last digit. Get the remainder mod 5. If it is 0 or 5, number is multiple of 5.

    ReplyDelete