CODEWITHSUNDEEP
bit-manipulationbitwise-operatorsbit
qdot
qdot

Reputation: 6335

Efficient (bit-wise) division by 24

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?

Upvotes: 2

Views: 1143

Answers (2)

Grizzly
Grizzly

Reputation: 20191

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.

Upvotes: 1

Oliver Charlesworth
Oliver Charlesworth

Reputation: 272447

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.

Upvotes: 4

Related Questions