About shift operator in C++

I am looking at big code base in C++. There i开发者_JS百科s line mentioned as below

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

Here theTrees is

vector<int> theTrees

What is statement 1 << theTrees.size( ) likely trying to achieve? Assume we have tree size of 25 elements.

If your question is about C++: 1<< is usually thought of as "2 to the *N*th power."

If your question is about data structures theory: a binary tree of height n has up to 2^i nodes per level, for up to 2^n - 1 nodes total.
(but you should have tagged it that way)

A left shift by n is basically multiplying by 2 to the nth power. Whenever you have 1 << n you're just calculating the nth power of 2. E.g.:

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

Etc.

I suspect theTrees.size() returns not the number of elements in the tree but the height of the tree (number of levels), because that's the only way this makes sense. Given a full binary tree, the number of nodes is 2^N - 1, where N is the height of the tree. E.g., a tree with three levels (n = 3) can hold 2^3 - 1 = 7 nodes. Check it: The first level has one, the second has two and the third has four. 1 + 2 + 4 = 7.

In binary, 1 is:

1

If we shift it left by one, 1 << 1 then we have:

10

Which is decimal 2. So shifting << 25 means we get:

10000000000000000000000000

Which is:

33554432

Similar to how in decimal if we shift left by one, we multiply by 10, doing so in binary multiplies by 2. So we get 2^25 essentially.

It computes two to the power of theTree.size() minus 1

I think in this case the size is actually the number of levels. Assuming you have a balanced binary tree this is the number of elements in the tree (if its full). For example a tree with only the head has 1 << 1 -1 = 1 possible nodes where as a full tree with 3 levels has 1 << 3 - 1 = 7 nodes (the head its two children and the children's four children)