Об операторе сдвига в C ++

Question

Я смотрю на большую кодовую базу в C ++. Существует строка, упомянутая ниже

int capacity( ) const
{
    return ( 1 << theTrees.size( ) ) - 1;
}

Здесь дерево есть

vector<int> theTrees

Что, вероятно, пытается достичь утверждение 1 << theTrees.size( )? Предположим, у нас есть дерево размером 25 элементов.

Answer 1

Если ваш вопрос касается C ++: 1<< обычно рассматривается как "от 2 до * N * th степени".

Если ваш вопрос касается теории структур данных: двоичное дерево высоты n имеет до 2 ^ i узлов на уровень, всего до 2 ^ n - 1 узлов.
(но вы должны были пометить это так)

Answer 2

Сдвиг влево на n в основном умножается на 2 до n-й степени. Всякий раз, когда у вас есть 1 << n, вы просто вычисляете n-ую степень 2. Например: 1002

1 << 0 = 1
1 << 1 = 2
1 << 2 = 4
1 << 3 = 8

Etc.

Я подозреваю, theTrees.size() возвращает не количество элементов в дереве, а высоту дерева (количество уровней), потому что это единственный способ, который имеет смысл. Для полного двоичного дерева число узлов равно 2 ^ N - 1, где N - высота дерева. Например, дерево с тремя уровнями (n = 3) может содержать 2 ^ 3 - 1 = 7 узлов. Проверьте это: у первого уровня есть один, у второго есть два, и у третьего есть четыре. 1 + 2 + 4 = 7.

Answer 3

Я думаю, что в этом случае размер на самом деле количество уровней. Предполагая, что у вас есть сбалансированное двоичное дерево, это количество элементов в дереве (если оно заполнено). Например, дерево только с головой имеет 1 << 1 -1 = 1 возможных узлов, в то время как полное дерево с 3 уровнями имеет 1 << 3 - 1 = 7 узлов (у головы два ребенка и у детей четыре ребенка)

Answer 4

Вычисляет два до степени theTree.size() минус 1

Answer 5

В двоичном виде 1 равно:

1

Если мы сдвинем его влево на единицу, 1 << 1, то получим:

10

Десятичное число 2.Таким образом, сдвиг << 25 означает, что мы получаем:

10000000000000000000000000

Что составляет:

33554432

Подобно тому, как в десятичной системе, если мы сдвигаемся влево на единицу, мы умножаем на 10, делая это вдвоичное умножается на 2. Таким образом, мы получаем 2 ^ 25 по существу.