关于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++中的移位运算符

回答

相关问题