CODEWITHSUNDEEP
algorithmmath32-bit
Michael Cooper
Michael Cooper

Reputation: 2315

How to compute (2^32)/n using 32-bit integers

I have a 32-bit timer which I want to overflow after n steps. This means each step should be (2^32)/n. However, if I try to compute this number using 32-bit integers, the compiler complains that (1<<32) is larger than the type I'm using.

I could come quite close to the answer I'm looking for by instead doing something like (~0)/n. However, it bugs me that in this case I would not get the correct answer when n is a power of 2, which means in those cases it would take one extra step for the timer to overflow.

Is there a simple expression to calculate (2^32)/n using only 32-bit integers?

Upvotes: 3

Views: 706

Answers (2)

rici
rici

Reputation: 241861

If you want the counter to overflow on precisely the nth step (when this is possible), then you need to compute ceil(232 / n). Consider the two possible cases:

  1. n is not a power of 2. In this case, n is not a factor of 232, and the ceiling of the division is exactly one more than the floor. Moreover, (using truncating integer division, as in C or Java) floor(232 / n) == floor((232 - 1) / n). So the desired step is (232 - 1)/n + 1.

  2. n is a power of 2. In this case, n precisely divides 232, and so (232 - 1) / n will be one less than 232 / n. So the desired step is (232 - 1)/n + 1. Conveniently, that's the same value as in the first case.

Note: As @greybeard notes in a comment, there no guarantee that an appropriate step size exists if n > 216. For larger n, the above procedure will compute the largest step size which guarantees that overflow will not occur before step n.

Upvotes: 4

anatolyg
anatolyg

Reputation: 28278

If you are using C as your programming language, you can use its unsigned arithmetic. Consider the following:

floor(232 / n) = floor((232 - n) / n + 1)

If your n has an unsigned type (e.g. uint32_t), then the mathematical expression 232 - n can be calculated as simply -n.

So in C:

uint32_t n = ...;
uint32_t d = (-n) / n + 1;

Alternatively:

uint32_t d = (0 - n) / n + 1;

You should document it well, because this is really obscure code.

Upvotes: 1

Related Questions