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$.


Solution 1:

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$.

Solution 2:

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$.

Solution 3:

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 */