having a number dividable

[electroRF]

Hi,
Say that you got a number N, and you want it to be dividable by other number M, and you know that M is a power of 2.

For example, N = 123, M = 64.

I'm trying to write an efficient C code to find the minimal number that is larger than N and is dividable by M.

in this case -> 128

I made a few tests and the following seems to work:

( N + (M-1) ) & ~(M-1)

you see any problem with that?

anything more efficient that that?

Thank you.

 

[NorthGuy]

If M is known at the compile time, (M-1) and ~(M-1) can be pre-calculated. Then it's only two operations at run-time. You cannot do that in one operation, so it is the most efficient.

If M is unknown at the compile time, there are two more operations to compute (M-1) and ~(M-1). There are only a handful possible values for M, so you could create a table with pre-computed values, but it'll probably take longer to fetch them from the table than to calclulate. So, I think in this case it's the most efficient way too.

Why do you want this to be efficient?

 

[electroRF]

Hi NorthGuy

Hope you got a good heat conductor nearby

Thanks a lot for your reply.

M is unknown at compile time.

As for efficiency,
For example, I'd not want to perform division when I can do shift right instead, that would be wrong programming in my opinion.

I think there's additional way, but it won't work if N=0:

((N-1) / M ) *M + M

But this way uses division and multiplying which makes it less time efficient.

 

[Pommie]

The number that fits your criteria is the first number bigger than N that has the same number of trailing zeroes as M. Your equation seems to accomplish that and so I think it's the most efficient way.

Mike.

 

[electroRF]

hi mike.

thats a nice point of view!!

Thanks

 

[NorthGuy]

((N-1) / M ) *M + M

But this way uses division and multiplying which makes it less time efficient.

In your case you can replace division and multiplication by shifts left/right, which is three operation. Also C doesn't provide an easy way to find the amount of shift.

But, this method will work with any M, although you will have to do division and multiplication. Instead of division and multiplication, you can also subtract a remainder.

Look, here you have a general (work with any Ms) solution, which is less efficient. And your first (work with specific Ms) solution, which is more efficient. This is very typical. If you want maximum efficiency you must get specific.

 

[misterT]

I'm trying to write an efficient C code to find the minimal number that is larger than N and is dividable by M.

This is just the same as "Rounding up to a multiple of a known power of 2"
There are two efficient solutions
(x+7) & (-8)
and
x + (-x & 7)

EDIT: Sorry, the solution rounds up to the next multiple of 8.. I think your first solution is good, because it looks very similar to that one.

 

[electroRF]

Thank you NorthGuy and T

NorthGuy,
You're right, the ((N-1) / M ) *M + M works for any M.
and I was wrong, it works also for N=0

T,
I didn't know that -X = ~(X-1).

Cool