How to check if given number is divisible of 15 in fastest way?

Question

Division in processor takes much time, so I want to ask how to check in fastest way if number is divisible of some other number, in my case I need to check if number is divisible by 15.

Also I've been looking through web and found fun ways to check if number is divisible of some number, but I'm looking for fast option.

NOTE: as division takes much time I'm looking for answer without / and %.

Answer 1

Multiplication takes less time then division, so you can try this:

inline bool divisible15(unsigned int x)
{
    //286331153 = (2^32 - 1) / 15
    //4008636143 = (2^32) - 286331153
    return x * 4008636143u <= 286331153u;
}

This way works because 2^32-1 (max 32-bit value) is divisible of 15, however if you take, for example 7, it would look like working, but wouldn't work in all cases.

EDIT: See this, it proves that this solution (on some compilers) is faster then module.

EDIT: Here is the explanation and the generalization.