Efficient (bit-wise) division by 24

Question

Coding for an embedded platform with no integer divisor (nor multiplier), is there a quick way to perform a 'divide by 24'?

Multiply by 24 is simply

int a;
int b = (a << 4) + (a << 3); // a*16 + a*8

But division? It's a really simple divisor, with only two bits set?

[Divide a number by 3 without using *, /, +, -, % operators](http://stackoverflow.com/q/11694546/995714), http://www.hackersdelight.org/divcMore.pdf — phuclv, Apr 05 '16 at 15:11

score 4 · Accepted Answer · answered Dec 07 '11 at 17:32

4

If you don't need the result to be bit-exact, then you could consider multiplying by 1/24:

uint16_t a = ...;

uint32_t b = (uint32_t)a * (65536L / 24);

uint16_t c = b / 65536;

Of course, if your platform doesn't have a hardware multiplier, then you will need to optimise that multiplication. As it turns out, (65536 / 24) is approximately equal to 2730, which is 101010101010 in binary. So that multiply can be achieved with 3 shifts and adds.

answered Dec 07 '11 at 17:32

Oliver Charlesworth

267,707
33
569
680

3 shifts and adds.. sorry for being such a newbie (trying to outperform a C18 compiler..) - how do you multiply by 2730 in 3 shifts and adds? I've tested on python that ((a/8)*683)/2048 is good enough for my purposes, and doesn't overflow 16bit for the range of 'a' that interest me, now just shoving it into bit operations. – qdot Dec 07 '11 at 18:01
@qdot: As you can see from the binary representation, 2730 = 10 * 273 = (8 + 2) * (256 + 16 + 1) (so actually four shifts and three adds). – Oliver Charlesworth Dec 07 '11 at 18:08
yeah. That was exactly what I've been missing fron the '3 shifts and adds'. Anyways, I got the compiler to help me out with efficient multiply, now the whole hand-tuned 576-choice switch statement is down from 180us to 21us. Not too bad for a 6MIPS core. – qdot Dec 07 '11 at 18:13

score 1 · Answer 2 · edited May 23 '17 at 12:15

1

Well first of all you can use the fact that 24=8*3, so you can divide by 8 using shifting once again: a / 8 == a >> 3. Afterwards you have to divide the result by 3. A discussion about how to do that efficiently can be found here. Of course if you are coding in c (or any other higher level language really), it might be worthwile to simply look at the compileroutput first, it is possible that the compiler already has some tricks for this.

edited May 23 '17 at 12:15

Community

1
1

answered Dec 07 '11 at 17:49

Grizzly

19,595
4
60
78

Yeah, I'm coding in C. No, the compiler just calls a helper long division function for a 'divide by 3', so no joy there. The 0xAAAB trick is great, see my comment above. – qdot Dec 07 '11 at 18:03

Efficient (bit-wise) division by 24

2 Answers2