Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

C quick calculation of next multiple of 4?

What's a fast way to round up an unsigned int to a multiple of 4?

A multiple of 4 has the two least significant bits 0, right? So I could mask them out and then do a switch statement, adding either 1,2 or 3 to the given uint.

That's not a very elegant solution..

There's also the arithmetic roundup:

 myint == 0 ? 0 : ((myint+3)/4)*4

Probably there's a better way including some bit operations?

like image 448
genesys Avatar asked Jan 07 '10 17:01

genesys


People also ask

How do you make a number multiple of 4?

To find the multiples of 4, multiply the numbers by 4. For example, multiplication of 4 by 9 gives 36, where 36 is a multiple of 4.

How do you find the next multiple of 5 from a number C#?

If the number isn't a multiple of 5 and you want to go to the next closest multiple, then do: num += (5 - (num % 5)).

What is next multiple of a number?

A multiple is the result of multiplying a number by an integer. In our case, the number we're multiplying by is six. The integers we've been multiplying by are 11 and 12. That means that the next integer we'll multiply by is 13.


4 Answers

(myint + 3) & ~0x03

The addition of 3 is so that the next multiple of 4 becomes previous multiple of 4, which is produced by a modulo operation, doable by masking since the divisor is a power of 2.

like image 138
JaakkoK Avatar answered Oct 01 '22 15:10

JaakkoK


I assume that what you are trying to achieve is the alignment of the input number, i.e. if the original number is already a multiple of 4, then it doesn't need to be changed. However, this is not clear from your question. Maybe you want next multiple even when the original number is already a multiple? Please, clarify.

In order to align an arbitrary non-negative number i on an arbitrary boundary n you just need to do

i = i / n * n;

But this will align it towards the negative infinity. In order to align it to the positive infinity, add n - 1 before peforming the alignment

i = (i + n - 1) / n * n;

This is already good enough for all intents and purposes. In your case it would be

i = (i + 3) / 4 * 4;

However, if you would prefer to to squeeze a few CPU clocks out of this, you might use the fact that the i / 4 * 4 can be replaced with a bit-twiddling i & ~0x3, giving you

i = (i + 3) & ~0x3;

although it wouldn't surprise me if modern compilers could figure out the latter by themselves.

like image 30
AnT Avatar answered Oct 01 '22 15:10

AnT


If by "next multiple of 4" you mean the smallest multiple of 4 that is larger than your unsigned int value myint, then this will work:

(myint | 0x03) + 1;
like image 37
Stephen C. Steel Avatar answered Oct 01 '22 13:10

Stephen C. Steel


(myint + 4) & 0xFFFC

like image 1
Michael Bray Avatar answered Oct 01 '22 13:10

Michael Bray