CODEWITHSUNDEEP
performancebinarynumbersbit-manipulationbitwise-operators
h4ckthepl4net
h4ckthepl4net

Reputation: 681

Check if number is multiple of 5 in most efficient way

Info

Hi everyone I was searching an efficient way to check if a number is multiple of 5. So I searched on google and found this solution on geeksforgeeks.org.

There were 3 solutions of my problem.

  1. First solution was to subtract 5 until reaching zero,
  2. Second solution was to convert the number to string and check last character to be 5 or 0,
  3. Third solution was by doing some interesting operations on bitwise level.

I'm interested in third solution as I can fully understand the first and the second.

Here's the code from geeksforgeeks.

bool isMultipleof5(int n) 
{ 
    // If n is a multiple of 5 then we
    // make sure that last digit of n is 0
    if ( (n & 1) == 1 )
        n <<= 1;

    float x = n;
    x = ( (int)(x * 0.1) ) * 10;

    // If last digit of n is 0 then n
    // will be equal to (int)x
    if ( (int)x == n )
        return true;
    return false;
}

I understand only some parts of the logic. I haven't even tested this code. So I need to understand it to use freely.

As said in mentioned article this function is multiplying number by 2 if last bit is set and then checking last bit to be 0 and returns true in that case. But after checking binary representations of numbers I got confused as last bit is 1 in case of any odd number and last bit is 0 in case of any even number. So...

Actual question is

What's the logic of this function?

Any answer is appreciated!

Thanks for all!

Upvotes: 0

Views: 1747

Answers (1)

jh316
jh316

Reputation: 951

  1. The most straightforward way to check if a number is a multiple of 5 is to simply
if (n % 5 == 0) {
    // logic...
}

What the bit manipulation code does is:

  1. If the number is odd, multiply it by two. Notice that for multiples of 5, the ones digit will end in either 0 or 5, and doubling the number will make it end in 0.
  2. We create a number x that is set to n, but with a ones digit set to 0. (We do this by multiplying n by 0.1, which removes the ones digit, and then multiply by 10 in order to add a 0, which has a total effect of just changing the ones digit to 0).
  3. We know that originally, if n was a multiple of 5, it would have a ones digit of 0 after step 1. So we check if x is equal to it, and if so, then we can say n was a multiple of 5.

Upvotes: 2

Related Questions