關於C++中的移位運算符

我正在研究C++中的大代碼庫。有行中提到如下關於C++中的移位運算符

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

這裏theTrees是

vector<int> theTrees

什麼是聲明1 << theTrees.size()可能想達到什麼目的？假設我們有25個元素的樹大小。

來源

2011-09-22 venkysmarty

n向左移動基本上乘以2第n個權力。只要你有1 << n你只是計算2.如的n次冪：

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

等等

我懷疑theTrees.size()回報樹中元素的數量不限，但樹的高度（數），因爲這是唯一的方法，這是有道理的。給定一個完整的二叉樹，節點的數量爲2^N - 1，其中N是樹的高度。例如，具有三個級別（n = 3）的樹可以容納2^3 - 1 = 7個節點。檢查一下：第一級有一個，第二個有兩個，第三個有四個。 1 + 2 + 4 = 7.

來源

2011-09-22 12:56:12

可能是一個明顯的答案愚蠢的問題，但正確的轉變，然後將2除以第n？ – MGZero

是的，並且顫抖着使用維基百科來獲取技術信息：「在一個二進制補碼的二進制數上右移n位具有將其除以2n的效果，但它總是向下舍入（朝負無窮大）。」來自http://en.wikipedia.org/wiki/Arithmetic_shift。知道舍入是重要的:)我也認爲1 >> 1 = 0，但它已經有一段時間了。 –

如果你的問題是關於C++的：1<<通常被認爲是「2到* N *次方」。

如果你的問題是關於數據結構理論：高度ñ的二叉樹每個級別最多2 ^我節點，長達2^N - 1個節的總。
（但你應該有標記的這種方式）

來源

2011-09-22 12:49:27

我不明白爲什麼在獲得容量方面我們正在做2到N次方。在這裏theTrees是矢量 theTrees – venkysmarty

@venkysmarty一個高度* n *的二叉樹每層最多有* 2^i *個節點，總共高達* 2^n-1 *個節點。 –

在二進制中，1：

如果我們轉移它由一個人留下，1 << 1則有：

哪是十進制的2。所以換擋<< 25意味着我們得到：

10000000000000000000000000

那就是：

33554432

方式類似，在小數，如果我們按有一個人留下，我們乘以10，通過2.二進制乘法這樣做所以本質上得到2^25。

來源

2011-09-22 12:50:14

它計算2到theTree.size()零下1

來源

2011-09-22 12:50:57

我認爲在這種情況下，大小實際上是級別數的電源。假設你有一個平衡的二叉樹，這是樹中元素的數量（如果它是完整的）。例如，只有頭部的樹有1 << 1 -1 = 1可能的節點，其中作爲具有3級的完整樹有1 << 3 - 1 = 7節點（其頭部的兩個孩子和孩子的四個孩子）

來源

2011-09-22 12:51:09 smitec

關於C++中的移位運算符

回答

相關問題