Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

4 Answers 4

up vote 8 down vote accepted

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

share|improve this answer
    
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$.

share|improve this answer
    
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 */
share|improve this answer
1  
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 ;-)

share|improve this answer
    
Thanks for the response. This was very informative –  Mrshll187 Jan 31 '13 at 17:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.