Recall that a number
y that has a rightmost bit can be written as y = d * 2n where d is odd. A number x is divisible by y = d * 2n iff it is divisible by 2n and by d. And both of those problems have already been solved in earlier posts, so:
bool IsDivisibleBy(uint32_t x, uint32_t divisor)
{
uint32_t poweroftwo = divisor & -divisor;
uint32_t d = divisor >> bsf(divisor);
return (x & (poweroftwo - 1)) == 0 &&
(d == 1 || IsDivisibleByOdd(x, d));
}Pretty straightforward. Except perhaps the
d == 1 bit. Recall that IsDivisibleByOdd doesn't want the divisor to be one, so that case has to be avoided. And if d is one, that means the divisor was a power of two. It even works if divisor is one; poweroftwo would also be one, and x & 0 is clearly always zero.And
bsf is not defined. The implementation would be strongly platform dependent, and not particularly enlightening.Now, on to the performance part. Does this help? The answer is the same as last time - no, usually not. Except in some select cases, such as when you need to test a whole array for divisibility by the same number, which is not a compile-time constant.
Added on 29 January 2014: as Jasper Neumann pointed out, if right-rotate can be used, the part that tests whether the lower bits are zero can be merged with the other test, as described in, for example, Hacker's Delight chapter 10-16 (Test for Zero Remainder after Division by a Constant) and gmplib.org/~tege/divcnst-pldi94.pdf.
That concludes the divisibility series (for now, anyway). Next post, something completely different.
