對于一個由0…n的所有數按升序組成的序列，我們要進行一些篩選，每次我們取當前所有數字中從小到大的第奇數位個的數，并將其丟棄。重復這一過程直到最后剩下一個數。請求出最后剩下的數字。

讓客戶滿意是我們工作的目標，不斷超越客戶的期望值來自于我們對這個行業(yè)的熱愛。我們立志把好的技術通過有效、簡單的方式提供給客戶，將通過不懈努力成為客戶在信息化領域值得信任、有價值的長期合作伙伴，公司提供的服務項目有：域名注冊、網頁空間、營銷軟件、網站建設、涿鹿網站維護、網站推廣。

輸入描述:

每組數據一行一個數字，為題目中的n(n小于等于1000)。

輸出描述:

一行輸出最后剩下的數字。

輸入例子:

500

輸出例子：

255

方法一：常規(guī)解法，將數組不斷更新，每一次去除奇位數的元素，直至數組的長度為1，輸出即可。
算法復雜度：
T（n） = n + n/2 + n/4 +…1 = 2^n-1
故為O（2^n）
時間復雜度：
O(n)
代碼：（偷個懶寫個python版）

n = int(input())
lis = [i for i in range(0,n+1)]
while len(lis)!=1:
    lis = [i for i in lis if (lis.index(i)+1)%2==0]
print(lis)

方法二：利用二進制巧妙解法
思路：
我們發(fā)現，每一次刪除的元素都是對應下標位置的二進制最右端為0的元素，列如0（二進制為0），2（二進制為10），4（二進制為100）。剩余的元素例如1（01），3（11），5（101）在下一次的變換中對應的二進制下標為原二進制下標左移一位之后的1（1），3（10），5（10）之后繼續(xù)刪除對應下標的二進制數的最右端為0的元素。所以最后剩下的元素，一定是從右往左數二進制數中含1最多的元素，因為每一次刪除移位后最右端都為1，會被一直保留下來
算法復雜度：
O(n)
空間復雜度:
O(1)

#includeusing namespace std;
int main(){int n;
	cin>>n;
	int x = 1;
	while( x<= n )
		x = x*2 +1;
	cout<< (x>>1)<< endl;
}

方法三：數學公式法
分析可知，每一次減少一半的數據，經過long(n)（向下取整）次減少到只有一個數。那么只有2^floor(log(n)) 或者 2^floor(log(n))-1 能夠經過long(n)次的向下取整之后得到1.因為在第一次刪除時，已經去除所有的偶數，因此排除2^{log(n))。所以這個數為2}log(n))-1
算法復雜度：
時間復雜度：O（1）
空間復雜度：O(1)

#includeusing namespace std;
int main(){int n;
	cin>>n;
	cout<<(int)pow(2,floor(log2(n)))-1<