CODEWITHSUNDEEP
c++bitwise-operatorsbit-shift
venkysmarty
venkysmarty

Reputation: 11431

About shift operator in C++

I am looking at big code base in C++. There is 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.

Upvotes: 3

Views: 234

Answers (5)

JB.
JB.

Reputation: 42094

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)

Upvotes: 6

i_am_jorf
i_am_jorf

Reputation: 54600

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.

Upvotes: 2

smitec
smitec

Reputation: 3049

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)

Upvotes: 2

Axel Gneiting
Axel Gneiting

Reputation: 5393

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

Upvotes: 2

Mike Kwan
Mike Kwan

Reputation: 24447

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.

Upvotes: 2

Related Questions