C++의 시프트 연산자에 대해서

C++에서 큰 코드베이스를보고 있습니다. 라인 여기C++의 시프트 연산자에 대해서

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

theTrees 다음과 같이이 언급 문 1 << theTrees.size() 가능성이 달성하려고 무엇

vector<int> theTrees

입니까? 트리 크기가 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은 트리의 높이입니다. 예를 들어, 3 레벨 (n = 3)의 트리는 2^3 - 1 = 7 노드를 수용 할 수 있습니다. 확인 : 첫 번째 레벨에는 1이 있고 두 번째 레벨에는 두 개가 있고 두 번째 레벨에는 네 개가 있습니다. 1 + 2 + 4 = 7.

출처

2011-09-22 12:56:12

명백한 대답으로 아마 어리석은 질문 일지 모르지만 오른쪽 시프 팅은 2로 나눌 것입니다. – MGZero

그래, 기술 정보를 위해 위키 피 디아를 사용하는 것을 떨쳐 버리고 : "2의 보수 부호있는 2 진수에 n 비트 씩 이동하는 것은 2n으로 나누는 효과가 있지만 항상 음의 무한대쪽으로 반올림합니다." http://en.wikipedia.org/wiki/Arithmetic_shift에서. 반올림을 아는 것은 중요합니다 :) 또한 1 >> 1 = 0이라고 생각합니다. –

C++에 관한 질문 : 1<<은 일반적으로 "2 * N * 제곱의 힘"으로 생각됩니다.

질문은 데이터 구조 이론에 대한 경우 : 높이 N의 이진 트리가 n은 최대 2 ^에 대한 레벨 당 최대 2^난 노드가 - 1 개 노드의 총.
는, 바이너리에서

출처

2011-09-22 12:49:27

용량을 얻는 데 왜 Nth의 제곱을하는지 알지 못합니다. 여기서 나무는 벡터 theTrees – venkysmarty

@venkysmarty 높이 * n *의 이진 트리에는 최대 * 2^n-1 * 노드까지 레벨 당 최대 * 2^i * 개의 노드가 있습니다. –

(그러나 당신이 그런 식으로 태그해야 1)은 다음과 같습니다

우리가 1 << 1는 우리가 한 번 왼쪽으로 이동하는 경우 :

어떤 십진수는 2입니다. 그래서 << 25를 이동하는 것은 의미 우리가 얻을 :

10000000000000000000000000

어느 : 우리는 하나 왼쪽 시프트 경우 소수, 우리는 2로 진 곱에 그렇게 10을 곱 방법

33554432

유사 그래서 근본적으로 2^25를 얻습니다.

출처

2011-09-22 12:50:14

그것은 내가 크기가 실제로 레벨의 수이 경우에 생각 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++의 시프트 연산자에 대해서

답변

관련 문제