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

6 Answers

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

<sub>Legend: C-like syntax: | bitwise OR, % modulo, x?y:z ternary ("if x then y else z"), == comparison.
* Generalized for any 2^𝑘.
More Info:</sub>

$\endgroup$ 4 $\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 $\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$

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

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy