题目描述
数学上把 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;
}
标签：输出,1075,幂次,30,寻找,距离,while,ans From： https://www.cnblogs.com/Ghost1GM/p/17607913.html