Recall that a number

`y`

that has a rightmost bit can be written as `y = d * 2`^{n}

where `d`

is odd. A number `x`

is divisible by `y = d * 2`^{n}

iff it is divisible by `2`^{n}

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.

## No comments:

## Post a Comment