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.

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.

Source (Stackoverflow)