Charles Charles - 10 months ago 42
C Question

2^n - 1 without overflowing a long

This is for a C89 project, in which

is defined if (and only if) a
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
which is guaranteed to be from 0 to 63 (inclusive) if
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
s are exactly 32 or 64 bits, this is undefined behavior. (In this part of the program
is almost impossible, but on a 32-bit computer
could definitely happen.) What's the right way to do this?

I suppose I could just test for
but that feels hacky.

hvd hvd
Answer Source

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

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.