accidental left shift of long long data type modifies seemingly unrelated variable

Question

I have the following code in which I accidently did left shifting instead of right shifting of the variable p.
However, when I ran the code, the pointer root was being reset to null (for input 2 and many others).
Shouldn't there be a segmentation fault, because of the array bits?
Could someone please explain this behaviour?

Thanks in advance.

#include <bits/stdc++.h>
using namespace std;

typedef struct $ {
    struct $* left;
    struct $* right;

    $(){
        left = NULL;
        right = NULL;
    }
} vertex;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long p;

    cin >> p;
    bool bits[30];

    vertex* root = new vertex();
    cout << "root: " << root << endl;

    int j = 0;

    while(p){
        bits[29 - j] = p&1;
        j++;
        p <<= 1;
    }

    cout << "root: " << root << endl;

    return 0;
}

What makes you think that "the pointer root was being reset to null"? — Yunnosch, Jan 11 '20 at 08:21
@Yunnosch Run the code, first print statement gives the address of the vertex obect, while the other print statement prints 0 — Arpit Bhadauria, Jan 11 '20 at 08:24
Unrelated to your problem, but please read [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) as well as [Why is “using namespace std;” considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) And don't use online competitive or judge sites as a learning resource. Instead take a few classes, or at the very least read [a couple of good books](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list/388282#388282). — Some programmer dude, Jan 11 '20 at 08:31
While `$` is legal, it does at first glance provoke the question "Is this C++ or bash?". Something to consider. Surely there is a more descriptive name for the `struct` that would be appropriate? — David C. Rankin, Jan 11 '20 at 08:41
@Someprogrammerdude I was actually writing the code for a competitive programming problem, where it is very common to use "#include " and "using namespace std" to avoid including many algorithms and data structures libraries per problem. It basically serves as a template for all problems. — Arpit Bhadauria, Jan 11 '20 at 09:30
I guessed. And that's just a bad habit that makes all your compiles take an exorbitant amount of time. Not to mention that bad habits (like good) tend to stay... Better use good habits everywhere. — Some programmer dude, Jan 11 '20 at 10:10
@DavidC.Rankin https://en.cppreference.com/w/cpp/language/identifiers lists the following as valid in identifiers: digits, underscores, lowercase and uppercase Latin letters, and a number of unicode characters which start at U+00AB. None of these include $. (I don't think $ is a portable name for a struct.) — Martin Bonner supports Monica, Jan 11 '20 at 11:29

Yunnosch · Accepted Answer · 2020-01-11T11:00:00.033

If you expect a segmentation fault in some siutation or another, you are very often disappointed. There is no guarantee for that, it would be too easy. Or to put it differently, guaranteeing it would be too costly.

Accessing an array outside of its range causes undefined behaviour and that means you are guaranteed that there is no guarantee.

https://en.wikipedia.org/wiki/Undefined_behavior

So because of UB, guessing at why anything in your case happens is actually wrong and does not really explain anything. It is kind of forbidden to even guess.

However, as long as you do not rely on it, here is some guessing, offered to minimise your frustration.

The way you define your variables is relevant.

bool bits[30];
vertex* root = new vertex();

In this order, the pointer root will, by many compilers/linkers, be put in memory on an address just lower than the array bits.
In that location it falls victim to being overwritten if you start writing at lower addresses than the array. Which you do here

bits[29 - j] = p&1;

when j is greater than 29. And that is very likely happening, because the loop condition does not guarantee to stop before that.
By the way, even with right shift, some inputs to a long long variable would require more than 29 shifts to end up 0.

I agree with Some, that you should not `#include `. I would be interested in where you picked that habit up. — Yunnosch, Jan 11 '20 at 08:34
Seems like it's taught at school, in some places: https://stackoverflow.com/q/31816095/10871073 — Adrian Mole, Jan 11 '20 at 08:36

0x4d45 · Answer 2 · 2020-01-11T11:17:08.390

In modern computer systems, memory is managed and allocated by the operating system in pages (usually of a size around 4 KB). A segmentation fault occurs when the memory management hardware (generally located within the CPU) catches a process accessing a memory page not belonging to it. This causes an interrupt, which the operating system then handles, usually by killing the violating process.

However, accessing data on your stack (whether on purpose or accidentally) cannot possibly cause a memory access violation, because - obviously - the stack is located within a memory page owned by you; otherwise you couldn't access data on the stack at all.

Notice, though, that if the top of the stack is near the border of two memory pages, it might be possible to cause a segmentation fault by accessing a memory location near the top of the stack (on the next page).

accidental left shift of long long data type modifies seemingly unrelated variable

2 Answers2