20
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ What is the answer for $n=24?$ $\endgroup$ Jan 31, 2013 at 17:09
  • 2
    $\begingroup$ @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 $\endgroup$
    – Mrshll187
    Jan 31, 2013 at 17:17
  • $\begingroup$ @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. $\endgroup$
    – SBF
    Jan 31, 2013 at 17:19

7 Answers 7

27
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ Nice, thanks for the response! Pretty clever $\endgroup$
    – Mrshll187
    Jan 31, 2013 at 17:39
  • 3
    $\begingroup$ Would you mind expanding on why does this work / how did you arrive at this solution $\endgroup$
    – vandre
    Jun 8, 2017 at 16:06
  • 1
    $\begingroup$ I am trying to find the multiple just below the given number. So that of the given number is 55, answer would be 48. Any help? $\endgroup$
    – devdoe
    Jul 2, 2017 at 5:36
  • 1
    $\begingroup$ @nr5 Given that this technique always gives us either the current multiple or the next highest, you can simply subtract the multiple from the result (and use max to ensure the result stays positive). In your example, ( ( x - 1 ) | 15 ) + 1 = 64, 64 - 16 = 48, max( 0, 48 ) = 48. The complete algorithm, where x is the value and m is the multiple, would be: max( 0, ( ( ( x - 1 ) | ( m - 1 ) ) + 1 ) - m ). $\endgroup$
    – Beejor
    Dec 29, 2018 at 23:01
  • $\begingroup$ This doesn't work when I change the multiple to 30. When I do this (100|29) + 1. I get 126, but it should be 120. What am I doing wrong? $\endgroup$
    – Donny V.
    Dec 4, 2019 at 3:38
12
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ This will most likely be my solution as soon as I can figure out how to turn it into C code $\endgroup$
    – Mrshll187
    Jan 31, 2013 at 17:28
  • $\begingroup$ See this question to see how to implement ceiling of integer division in C. $\endgroup$
    – cubuspl42
    Aug 9, 2015 at 20:34
  • $\begingroup$ How do you find largest multiple of 16 not larger than $n$? $\endgroup$
    – David G
    Sep 21, 2017 at 11:23
  • $\begingroup$ @David n - n%16 $\endgroup$
    – Leponzo
    Apr 5, 2021 at 14:39
10
$\begingroup$

A summary of some of the other code, plus a few related items.

Find the nearest multiple of M

For a given number X:

( x - ( x % m ) )

At or above a given number X*:

( ( x - 1 ) | ( m - 1 ) ) + 1

Below a given number X*:

max( 0, ( ( x - 1 ) | ( m - 1 ) ) + 1 - m )

Test if X is a multiple of M

( x % m == 0 )

Round X to the nearest multiple of M

Standard rounding:

( m == 0 ) ? x : floor( ( x / m ) + 0.5 ) * m

Down to the nearest multiple (floor, toward -inf):

( m == 0 ) ? x : floor( x / m ) * m

Up to the nearest multiple (ceil, toward +inf):

( m == 0 ) ? x : ceil( x / m ) * m

Legend: C-like syntax: | bitwise OR, % modulo, x?y:z ternary ("if x then y else z"), == comparison.
* Generalized for any 2𝑘.
More Info: math.stackexchange.com/questions/1798899

$\endgroup$
4
  • 2
    $\begingroup$ I just wanted to add that when using the "Round X to the nearest multiple of M" option. If you remove the 0.5 you will always get the nearest lower number. To get the nearest higher number replace 0.5 with 1. $\endgroup$
    – Donny V.
    Dec 4, 2019 at 4:53
  • $\begingroup$ @DonnyV. Thanks! I've added your notes to the post. You can also force rounding to the next multiple (one over/under the nearest) like floor( ( x / m ) + 1 ) * m or floor( ( x / m ) - 1 ) * m, respectively. $\endgroup$
    – Beejor
    Jan 5, 2020 at 19:51
  • 1
    $\begingroup$ This bitwise OR method does not work when M is not a power of 2 according to math.stackexchange.com/a/3491658/185886. $\endgroup$
    – Leponzo
    Apr 5, 2021 at 14:32
  • 1
    $\begingroup$ Update: I corrected my answer based on feedback. Apparently the bitwise OR method only works if the multiple is a power of 2. If anyone wants to add the non-generalized-for-2 cases for under/over, please feel free. Thanks! $\endgroup$
    – Beejor
    Oct 11, 2021 at 19:58
7
$\begingroup$

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 */
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – user856
    Jan 31, 2013 at 17:28
  • $\begingroup$ Thanks for your responses. I appreciate it $\endgroup$
    – Mrshll187
    Jan 31, 2013 at 17:32
1
$\begingroup$

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 ;-)

$\endgroup$
2
  • $\begingroup$ Thanks for the response. This was very informative $\endgroup$
    – Mrshll187
    Jan 31, 2013 at 17:44
  • $\begingroup$ Unless there's some advantage to doing it with AND, using OR seems to yield the same result but with less ops/complexity. For example, where N = number, X = multiple: ( ( N - 1 ) | ( X - 1 ) ) + 1 (vs) N - ( N & ( X - 1 ) ) + ( ( N & ( X - 1 ) ) + ( X - 1 ) ) & X ). $\endgroup$
    – Beejor
    Dec 29, 2018 at 22:38
1
$\begingroup$

Other answers and comments saying that the bitwise or approach works in the general case are wrong.

Consider $x = 1000, m = 3$

( 1000 | (3-1) ) + 1 == 1003
1003 % 3 != 0

This method works in the general case while keeping us type stable (i.e. no need for float division):

x - x % m
$\endgroup$
3
  • 1
    $\begingroup$ Nobody is claiming that the bitwise OR works in the general case – it does, however, always work when $m$ is a power of $2$. $\endgroup$
    – ViHdzP
    Dec 30, 2019 at 2:45
  • 1
    $\begingroup$ At the time of writing, there is an answer that starts: "To summarize some of the other code, plus a few related items. Find the nearest multiple of M, at or above a given number X" $\endgroup$
    – cmc
    Jan 2, 2020 at 18:08
  • 1
    $\begingroup$ This is the one. $\endgroup$
    – Leponzo
    Apr 5, 2021 at 14:41
1
$\begingroup$

The answer by Hagen of ((𝑥−1)|15)+1 uses a -, |, and + operation; however, I use the following:

  (x+15) & -16

This form uses only a + and an & operation, everything else is a constant.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .