Why is 0x7FFFFFFFull | (1 << 31) returning 0xFFFFFFFFFFFFFFFF in C++?

Question

When I do (0x7fffffff | 0x8000000) I am getting 0xffffffffffffffff instead of the expected 0xffffffff. What am I missing?

Some sample code and output to illustrate my question.

Code:

#include <iostream>

using namespace std;

int main()
{
        unsigned long long val = 0;

        for (int i = 0; i < 64; i++) {
                val |= 0x1 << i;
                cout << i << ": " << std::hex << val << std::dec << endl;
        }

        return 0;
}

Output:

0: 1
1: 3
2: 7
3: f
4: 1f
5: 3f
6: 7f
7: ff
8: 1ff
9: 3ff
10: 7ff
11: fff
12: 1fff
13: 3fff
14: 7fff
15: ffff
16: 1ffff
17: 3ffff
18: 7ffff
19: fffff
20: 1fffff
21: 3fffff
22: 7fffff
23: ffffff
24: 1ffffff
25: 3ffffff
26: 7ffffff
27: fffffff
28: 1fffffff
29: 3fffffff
30: 7fffffff
31: ffffffffffffffff
32: ffffffffffffffff
33: ffffffffffffffff
34: ffffffffffffffff
35: ffffffffffffffff
36: ffffffffffffffff
37: ffffffffffffffff
38: ffffffffffffffff
39: ffffffffffffffff
40: ffffffffffffffff
41: ffffffffffffffff
42: ffffffffffffffff
43: ffffffffffffffff
44: ffffffffffffffff
45: ffffffffffffffff
46: ffffffffffffffff
47: ffffffffffffffff
48: ffffffffffffffff
49: ffffffffffffffff
50: ffffffffffffffff
51: ffffffffffffffff
52: ffffffffffffffff
53: ffffffffffffffff
54: ffffffffffffffff
55: ffffffffffffffff
56: ffffffffffffffff
57: ffffffffffffffff
58: ffffffffffffffff
59: ffffffffffffffff
60: ffffffffffffffff
61: ffffffffffffffff
62: ffffffffffffffff
63: ffffffffffffffff

Answer 1

Firstly your code does not do what you say in your title/question; I have edited the title.

The problem is 1 << 31. If you have 32-bit int (which apparently you do, judging by the results), this cause arithmetic overflow. In C++14 this is implementation-defined behaviour; prior to C++14 it causes undefined behaviour. Reference.

Usually the implementation-defined behaviour will be to generate the int with the sign bit set and the other bits unset. In 2's complement this value is INT_MIN. You then perform arithmetic between an unsigned long long and an int. This is defined as: the int is converted to unsigned long long.

Converting signed integers to unsigned is done by wrapping it around (modular arithmetic) modulo ULLONG_MAX+1. So the result of (unsigned long long)INT_MIN is a very large positive number, in fact 0xFFFFFFFF80000000. (To check this, add 0x80000000 to it to get 0).

So you are actually doing 0x7FFFFFFF | 0xFFFFFFFF80000000 which gives the observed result.

---

Later on it gets worse: 1 << 32 and larger causes undefined behaviour due to shifting by the whole width of the type.

To fix this, change 0x1 in your code to 1ull. The you will be shifting an unsigned long long, instead of an int.

Answer 2

because of sign extension val is an unsigned long long. But val is not what you are shifting. You are shifting 0x1, an int, then extending it to long long for the '|='