Bitwise division | Hummus and Magnets

Integer division is dear. Way more costly than multiplication. A lot, rather more costly than addition. Should you’re making an attempt to make some integer operations actually quick it’s dangerous information if you want to do division.

Some time in the past, for a pastime challenge, I occurred to be taking part in round with variable-length integer encodings. The place you retailer integers such that small ones take up much less house than massive ones. That is the type of factor you wish to be very quick certainly. At one level I ended up with this expression on a scorching code path:

(63 - nlz) / 7

For every thing else I may provide you with quick methods of doing it utilizing bitwise operations however this one place I ended up with division. And on this case not solely is it costly it’s overkill: the worth we’re dividing by is a continuing and on this case nlz is thought to be between 0 and 63.

I believed: I’ll experiment a bit and see if I can’t provide you with some bitwise operations that work identical to dividing by 7 when the enter is between 0 and 63. The one type of division that could be very low cost is by an influence of two, that’s simply bit shifting. And it occurs to be the case that 7 * 9 = 63, which is nearly 64, an influence of two. Placing these collectively I obtained one thing I believed would possibly do the trick:

This you possibly can compute with bitwise operations!

(9 * v) / 64
= (9 * v) >> 6
= (v + 8 * v) >> 6
= (v + (v << 3)) >> 6

Not dangerous! An expression that’s purely bitwise operations however that computes nearly division by 7. How “nearly”? It seems that this works for 0 to 6 however provides the mistaken reply for 7: it yields 0 the place it ought to be 1. Okay, it’s off by 1 — let’s strive including 1 then:

(v + (v << 3) + 1) >> 6

Now it’s right from 0 to 13 however provides the mistaken reply for 14: 1 the place it ought to be 2. So let’s strive including 2 as a substitute of 1. That makes it really works for 0 to 20. If we maintain growing the fudge issue so long as we maintain getting the suitable reply we find yourself with:

(v + (v << 3) + 9) >> 6

This computes v / 7 appropriately for v from 0 to 69 which was what I wanted initially. Really I solely wanted as much as 63.

Glorious! Drawback solved! So let’s get again to varint encoding? Effectively, now I used to be on my means down the rabbit gap of bitwise division. What if it wasn’t 7 I wanted to divide by, may I do one thing related for different values? The place did the restrict of 69 come from, and the fudge issue of 9?

Let’s generalize

A fast recap: as a result of 7 * 9 = 64 - 1 we are able to implement v / 7 like this:

(9 * v + 9) / 64
= (v + (v << 3) + 9) >> 6

for v between 0 and 69.

Put extra abstractly: given a divisor d, which occurred to be 7, we discovered an influence of two, 64 = 2⁶, such that

for a multiplier worth m which on this case was 9.

Utilizing this along with a fudge issue a which additionally turned out to be 9, we had been capable of exchange division by d with

(m * v + a) >> n

which provides the right outcome for values between 0 and a few restrict L, the place L on this case was 69.

Now, what if I wished to divide by another worth than 7? Let’s say 43? Then we’ve to search out an n such that

for some m. That simply means an n such that 43 is a consider 2ⁿ-1. I’ve put a desk of the prime components of twoⁿ-1s on the backside. There’s one: 2¹⁴-1.

So you possibly can exchange v / 43 with

(381 * v + a) >> 14

for some selection of a, after which will probably be right for values as much as some restrict L. What ought to a be and what’s going to that make L? Effectively, let’s attempt to derive them. Let’s begin with a. (And simply skip the derivations if this type of stuff bores you).

One factor that positively should maintain is that if you happen to bitwise-divide 0 by d the outcome have to be 0:

(m * 0 + a) >> n = 0

So we all know that positively the fudge issue have to be non-negative. Equally if you happen to bitwise-divide d-1 by d the outcome should even be 0; that offers us:

(m * (d - 1) + a) >> n = 0

Placing these two collectively we get that

See Also

Sit. · Rafał Pastuszak

However which a to decide on? There we are able to use the truth that bitwise division will increase extra slowly then actual division so when it will get the reply mistaken, it’ll be as a result of it returns too small a worth. So we wish a to be the biggest allowed worth: m.

Subsequent, let’s derive L. Or, let’s derive L+1, the primary worth the place bitwise division yields the mistaken outcome. Since bitwise division grows extra slowly than division that might be at some a number of of d, ok d, the place it yields a worth lower than the true outcome: ok – 1.

(m * ok * d + m) >> n = ok - 1

The smallest ok which yields a mistaken result’s therefore the primary worth better than m: m + 1 in order that makes L:

L + 1 = ok * d
L + 1 = (m + 1) * d
L = (m + 1) * d - 1

Simply to confirm let’s strive the instance from earlier than: 7

L = (9 + 1) * 7 - 1
= 69

One other helpful solution to write that is

L = (m + 1) * d - 1
= (m * d) + d - 1
= 2n - 1 + d - 1
= 2n + (d - 2)

Because of this for any d > 2 L is a minimum of 2ⁿ. That offers a pleasant rule of thumb: the bitwise division by 43 above holds for all values as much as 2¹⁴. After which a bit extra.

Are you able to all the time discover a worth of n that permits you to do bitwise division? In idea most likely sure, I’m not ok at quantity idea to say definitively. However since in follow we’re working with finite numbers you normally need n to be lower than 32 after which the reply, a minimum of initially, is not any. Listed here are some values you could’t bitwise divide with an n at most 32:

37, 53, 59, 61, 67, 71, 79, 83, 97

Does that imply that if we find yourself having to divide by 37 there isn’t any solution to specific that as a bitwise operation? No. This actual method doesn’t work however there are others. As an example, to date we’ve solely checked out dm = 2ⁿ-1. There’s additionally dm = 2ⁿ+1 — possibly we are able to use that when 2ⁿ-1 doesn’t work? (Spoiler: sure we are able to, not all the time however typically). What about dm = 2ⁿ-2, would possibly that be helpful someway? There’s extra enjoyable available with this. However that’s for an additional publish.

Appendix

Prime components of twoⁿ – 1 for n as much as 32 (Mersenne primes marked in daring).

Reverse index: for a primary, which 2ⁿ-1s is it an element of: