случайное смещение влево типа long long изменяет, казалось бы, не связанную переменную

Question

У меня есть следующий код, в котором я случайно сделал сдвиг влево вместо сдвига вправо переменной p.
Однако, когда я запустил код, указатель root сбрасывался на ноль (для входа 2 и многие другие).
Не должно ли быть ошибки сегментации из-за битов массива?
Может кто-нибудь объяснить это поведение?

Заранее спасибо.

#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;
}

Answer 1

Если вы ожидаете ошибки сегментации в той или иной ситуации, вы очень часто разочаровываетесь. На это нет никаких гарантий, это было бы слишком просто. Или, иначе говоря, гарантируя, что это будет слишком дорого.

Доступ к массиву за пределами его диапазона вызывает неопределенное поведение, и это означает, что вы гарантированно, что нет гарантии.

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

Так что из-за UB угадать, почему что-то в вашем случае происходит, на самом деле неправильно и ничего не объясняет. В некотором смысле запрещено даже догадываться.

Однако, пока вы не полагаетесь на это, вот некоторые догадки, предлагаемые, чтобы минимизировать ваше разочарование.

Способ определения переменных

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

В этом порядке многие компиляторы / компоновщики будут указывать в память указатель * 1017 по адресу, который находится чуть ниже массива bits.
. местоположение, оно становится жертвой перезаписи, если вы начинаете писать по более низким адресам, чем массив. Что вы делаете здесь

bits[29 - j] = p&1;   

, когда j больше 29. И это очень вероятно, потому что условие l oop не гарантирует остановку до этого.
Кстати даже при сдвиге вправо для некоторых входов в длинную длинную переменную потребуется более 29 сдвигов, чтобы в итоге получилось 0.

Answer 2

В современных компьютерных системах память управляется и распределяется операционной системой в страниц (обычно размером около 4 КБ). Ошибка сегментации возникает, когда аппаратное обеспечение управления памятью (обычно расположенное в ЦП) перехватывает процесс, обращающийся к странице памяти, не принадлежащей ему. Это вызывает прерывание, которое затем обрабатывает операционная система, обычно убивая нарушающий процесс.

Однако доступ к данным в вашем стеке (как умышленно, так и случайно) не может вызвать нарушение доступа к памяти, потому что - очевидно - стек находится на странице памяти, принадлежащей вам; в противном случае вы вообще не могли бы получить доступ к данным в стеке.

Обратите внимание, однако, что если вершина стека находится вблизи границы двух страниц памяти, возможно, возникнет ошибка сегментации при доступе ячейка памяти около вершины стека (на следующей странице).