【二叉樹】二叉樹

題目描述

如上所示，由正整數1，2，3……組成了一顆特殊二叉樹。我們已知這個二叉樹的最後一個結點是n。現在的問題是，結點m所在的子樹中一共包括多少個結點。
比如，n = 12，m = 3那麼上圖中的結點13，14，15以及後面的結點都是不存在的，結點m所在子樹中包括的結點有3，6，7，12，是以結點m的所在子樹中共有4個結點。
           

輸入

輸入資料包括多行，每行給出一組測試資料，包括兩個整數m，n (1 <= m <= n <= 1000000000)。最後一組測試資料中包括兩個0，表示輸入的結束，這組資料不用處理。 
           

輸出

對于每一組測試資料，輸出一行，該行包含一個整數，給出結點m所在子樹中包括的結點的數目。
           

樣例輸入

3 7
142 6574
2 754
0 			
           

樣例輸出

3
63
498
           

#include <cstdio> 

int main(int argc, char** argv) {
 int m,n,count,s,now,i;
 while(scanf("%d%d",&m,&n) && (m != 0 || n != 0)){
  s = 0;
  i = m;
  while(i < n){  //求子樹的層數 
   i = i * 2 + 1;
   s++;
  }
  count = 0;
  now = 1;
  for(i = s - 1; i > 0; --i){ //最後一層不一定為滿 
   count += now;
   now = now * 2; 
  }
  count += now; 
  now = now * 2;
  if(now * m <= n)
   count += n - (now * m) + 1;//加上最後一層的結點 
  printf("%d\n",count);
 }
 return 0;
}