Charles Charles - 2 months ago 7
C Question

2^n - 1 without overflowing a long

This is for a C89 project, in which

LONG_IS_64BIT
is defined if (and only if) a
long
is 64-bit, that is, contains all the integers from -2^63-1 to 2^63-1. Otherwise (by the C standard) it contains all the integers from -2^31-1 to 2^31-1.

I have a number
n
which is guaranteed to be from 0 to 63 (inclusive) if
LONG_IS_64BIT
is defined or 0 to 31 (inclusive) otherwise. I would like to compute 2^n-1, which fits inside a long.

At the moment the code has
(1L<<n) - 1
, but in the highly-likely case that
long
s are exactly 32 or 64 bits, this is undefined behavior. (In this part of the program
n==63
is almost impossible, but on a 32-bit computer
n==31
could definitely happen.) What's the right way to do this?

I suppose I could just test for
n==31
and
n==63
but that feels hacky.

hvd hvd
Answer

If you know the mathematical value of (1L<<n)-1 fits in long, you can ensure you don't overflow by calculating the value minus one, and then adding one, rather than calculating the value plus one, and then subtracting one.

n == 0 ? 1 : ((1L<<n-1)-1<<1)+1

It's convoluted, requiring special casing to avoid left shift by a negative value if n == 0, but at least it gets you the value you need.

Alternatively, you can use a right shift:

#ifdef LONG_IS_64BIT
0x7FFFFFFFFFFFFFFF>>(63-n)
#else
0x7FFFFFFF>>(31-n)
#endif

You can't use LONG_MAX here if it could well be larger than you expect.

Realistically though, @melpomene's comment to use unsigned long should be good enough. The platforms where it has the same amount of value bits as long were already uncommon back when the standard was written. And if you already sort of assume long will have exactly 32 or exactly 64 bits, you probably shouldn't worry about the more esoteric implementations.

Comments