integer overflow in C# with left shift

Question

I have the following line of code in C#:

ulong res = (1<<(1<<n))-1;

for some integer n.

As long as n is lower than 5, I get the correct answer. However, for n>=5, it does not work.

Any idea, using bitwise operators, how to get the correct answer even for n=5 and n=6? For n=6, the result should be ~0UL, and for n=5, the result should be 0xFFFFFFFF.

Answer 1

As long as n is lower than 5, I get the correct answer. However, for n>=5, it does not work.

Well, it obeys the specification. From section 7.9 of the C# 5 spec:

The << operator shifts x left by a number of bits computed as described below.

For the predefined operators, the number of bits to shift is computed as follows:

• When the type of x is int or uint, the shift count is given by the low-order five bits of count. In other words, the shift count is computed from count & 0x1F.

So when n is 5, 1 << n (the inner shift) is 32. So you've then got effectively:

int x = 32;
ulong res = (1 << x) - 1;

Now 32 & 0x1f is 0... hence you have (1 << 0) - 1 which is 0.

Now if you make the first operand of the "outer" shift operator 1UL as suggested by p.s.w.g, you then run into this part of the specification instead:

• When the type of x is long or ulong, the shift count is given by the low-order six bits of count. In other words, the shift count is computed from count & 0x3F.

So the code will do as it seems you expect, at least for n = 5 - but not for n = 6.