對于一個由0…n的所有數(shù)按升序組成的序列，我們要進行一些篩選，每次我們?nèi)‘斍八袛?shù)字中從小到大的第奇數(shù)位個的數(shù)，并將其丟棄。重復(fù)這一過程直到最后剩下一個數(shù)。請求出最后剩下的數(shù)字。

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

輸入描述:

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

輸出描述:

一行輸出最后剩下的數(shù)字。

輸入例子:

500

輸出例子：

255

方法一：常規(guī)解法，將數(shù)組不斷更新，每一次去除奇位數(shù)的元素，直至數(shù)組的長度為1，輸出即可。
算法復(fù)雜度：
T（n） = n + n/2 + n/4 +…1 = 2^n-1
故為O（2^n）
時間復(fù)雜度：
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ā)現(xiàn)，每一次刪除的元素都是對應(yīng)下標位置的二進制最右端為0的元素，列如0（二進制為0），2（二進制為10），4（二進制為100）。剩余的元素例如1（01），3（11），5（101）在下一次的變換中對應(yīng)的二進制下標為原二進制下標左移一位之后的1（1），3（10），5（10）之后繼續(xù)刪除對應(yīng)下標的二進制數(shù)的最右端為0的元素。所以最后剩下的元素，一定是從右往左數(shù)二進制數(shù)中含1最多的元素，因為每一次刪除移位后最右端都為1，會被一直保留下來
算法復(fù)雜度：
O(n)
空間復(fù)雜度:
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;
}

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

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