How to find the nearest multiple of 16 to my given number n

If I'm given any random $n$ number. What would the algorithm be to find the closest number (that is higher) and a multiple of 16.

Example $55$

Closest number would be $64$

Because $16*4=64$

Not $16*3=48$ because its smaller than $55$.

-
What is the answer for $n=24?$ –  Ross Millikan Jan 31 '13 at 17:09
@RossMillikan This would fail my computation. This questions pertains to AES encryption block sizes. They need to be a multiple of 16. So if I had 55bytes I would have to go to the next nearest multiple that is higher then n. Thus failing my requirement –  Mrshll187 Jan 31 '13 at 17:17
@RossMillikan: as it is mentioned in OP, the number has to be higher than $n$ - and the closest higher multiple of $16$ is defined uniquely. –  Ilya Jan 31 '13 at 17:19

As you are surely trying to do this in a computer program, try the following C expression: $(x|15)+1$. This will always increase, even if $x$ is already a multiple of $16$.

Or try $((x-1)|15)+1$ if you don't want to increase the number if it is already a multiple of $16$.

-
Nice, thanks for the response! Pretty clever –  Mrshll187 Jan 31 '13 at 17:39

Use $16\lceil\frac{n}{16}\rceil$ to find the smallest multiple of $16$ not smaller than $n$, where the ceiling function $\lceil x\rceil$ denotes the smallest integer not smaller than $x$.

Use $16\lfloor\frac{n}{16}\rfloor+16$ to find the smallest multiple of $16$ larger than $n$, where the floor function $\lfloor x\rfloor$ denotes the largest integer not larger than $x$.

-
This will most likely be my solution as soon as I can figure out how to turn it into C code –  Mrshll187 Jan 31 '13 at 17:28

If you are expressing the number in binary format, you could throw out the last 4 bits and add one and multiply by 16. This does assume that given a multiple of 16, the number desired is strictly higher. If in the case where n is a multiple of 16 the answer should be n, then you'd have to check first if the last 4 bits are all zero.

So, in the case of 55 which is 110111 in base 2, this would then becomes 11 in base 2 which is 3 and then adding one gives 4 which times 16 produces 64.

There are Bitshift operators in C that could be used so you could have a function that takes in a parameter then performs the following series of operations(using Rn's suggestion):

int a;
a = n-1;
a = a >> 4; /* which is the same as dividing by 16. */
a = a + 1;
return a << 4; /* which is the same as multiplying by 16 */

-
Without needing any checks, you can do: subtract one, right shift by four, add one, left shift by four. This works for multiples of $16$ too. –  Rahul Jan 31 '13 at 17:28
Thanks for your responses. I appreciate it –  Mrshll187 Jan 31 '13 at 17:32

Using & as bitwise AND, let a = n & 15, then n - a + ((a+15) & 16) is what you are looking for (it can be generalized for any $2^k$).

I hope this helps ;-)

-
Thanks for the response. This was very informative –  Mrshll187 Jan 31 '13 at 17:44