Why do I need to subtract two from 1 << 64 to get 2^64 - 1?

Question

Every line of the output of this program is equal to 2 ^ i - 2, except for the last line, which is equal to 2 ^ 64 - 1. Why is that?

#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>

int main(void) {
    unsigned long long ONE = 1;
    unsigned long long i;
    for (i = 1; i <= 64; i++) {
        printf("%"PRIu64"\n", (ONE << i) - 2);
    }

    return EXIT_SUCCESS;
}

Output:

0
2
6
14
30
62
126
254
510
1022
2046
...
4611686018427387902
9223372036854775806
18446744073709551615

I'm pretty sure shifting by 64 bits results in undefined behavior. Have you tried shifting 64 bits total, but in multiple steps? — Dennis Meng, Aug 30 '13 at 01:14
`unsigned long long i <<= 63; i <<= 1;` works where `unsigned long long i <<= 64;` doesn't - you're right, thanks. Do you know where I can read more about this? — Kiwi, Aug 30 '13 at 01:20
The answers already link to helpful resources, so I won't bother to clutter this question up with more. — Dennis Meng, Aug 30 '13 at 01:22

score 5 · Answer 1 · edited Jun 20 '20 at 09:12

5

You are left shifting 64 to a 64-bit type(unsigned long long on your machine), it's undefined behavior.

BTW, unsigned long long ONE = 1; is bad coding style, you can simply use 1ULL.

C11 §6.5.7 Bitwise shift operators

The integer promotions are performed on each of the operands. The type of the result is that of the promoted left operand. If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined.

edited Jun 20 '20 at 09:12

Community

1
1

answered Aug 30 '13 at 01:17

Yu Hao

119,891
44
235
294

1

Bad coding style? It may be the single worst line of code I've ever read! In terms of characters to meaningful-content ratio, its about **26:1** – abelenky Aug 30 '13 at 01:21
2

@abelenky Hey don't blame the guy who didn't design the language keywords. – Neil Kirk Aug 30 '13 at 01:24
It _may_ be bad style but it works fine, the integer promotion rules make it very well defined, and `ULL` _could_ be considered unnecessary code clog. I'd be more worried about a variable called `ONE` especially when you have to change its value to `2` :-) – paxdiablo Aug 30 '13 at 01:27
1

@paxdiablo That is exactly what I mean, using `ONE` as variable name: in this case a constant may be what is needed. In other cases, a meaningful variable name is needed. Good point on `ULL` is unnecessary. – Yu Hao Aug 30 '13 at 01:30

score 4 · Accepted Answer · answered Aug 30 '13 at 01:19

Assuming yout ULL type is 64 bits wide, you're into undefined behaviour territory. As per C11 6.5.7 Bitwise shift operators:

If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined.

What's possibly happening is that the shift value is being reduced modulo 64, and 64 % 64 is zero. Hence, it's just evaluating ONE - 2 which is wrapping to 2⁶⁴-1. But, in all honesty, it could just be plucking that result out of the air since UB imposes no real restrictions :-)

score 1 · Answer 3 · edited May 23 '17 at 10:25

1

1ULL<<64 is undefined while shifting by less is defined.

See Is Shifting more than 32 bits of a uint64_t integer on an x86 machine Undefined Behavior? for more detail on the language standard.

edited May 23 '17 at 10:25

Community

1
1

answered Aug 30 '13 at 01:21

Liudvikas Bukys

5,790
3
25
36

score 0 · Answer 4 · answered Aug 30 '13 at 01:22

You reached the bit limit of 64bit (long long). Apparently 2^63 shift left causes a rollover, resulting in 2^0 = 1.

1 - 2 = -1 which, when treated as unsigned (assuming long long) is 2^64-1.

This result is interesting, since a non rollover implementation of shift left would result in 0, instead of 1, which after the substraction would result on 2^64-2.

Why do I need to subtract two from 1 << 64 to get 2^64 - 1?

4 Answers4