题目描述
数学上把 2 的 K 次方叫 2 的 K 次幂，如 4、8、32等。
给定一个整数 n ，请输出距离它最近的那个 2 的幂是多少。
如果有两个距离相同，输出那个小的。
输入
只有一个整数 n（10≤n≤2×10^9）
输出
只有一个整数，表示距离最近的那个 2 的幂。
样例
输入
17
输出
16
看到这题，我眉头紧皱，一道题看着就没什么难度，居然是基础题，值2金币？
然后写了一遍提交发现确实不那么容易。
首先求2的幂次这个肯定都会，先求出比n小的最大的那个幂次记为ans，然后看看题目，题目说“如果有两个距离相同，输出那个小的。”，所以我们还得看看ans*2的值，比较一下两者距离n哪个更近。
用while求解，时间复杂度是O(log2n),差不多就30次循环左右吧，但是我突然想到，2的幂次和2进制似乎有些关联，用while把n的二进制最后一个1删掉，只留下最高位的1不就是比n小的最大的那个幂次吗？数据上限2^9转换成2进制是1110111001101011001010000000000，一共31位，有13个1，最差情况是INT_MAX/2这个30位1的情况，
时间复杂度在O(30)以下。
#include<bits/stdc++.h> using namespace std; int n,n1; long long ans,ans1; int main() { scanf("%d",&n); //保存下n的值 n1=n; while(n) { //求n的最低位n&-n //消去最低位的1只需要两者相减即可 n-=(n & -n); if(n)ans=n; } //左移1位相当于乘2 ans1=ans<<1,n=n1; if(n-ans <= ans1-n)printf("%lld",ans); else printf("%lld",ans1); return 0; }