【题目描述】 很简单，判断数N是不是2的次方。 【输入格式】 第一行一个整数T表示数据的个数 接下来T行，每行一个正整数N 【输出格式】 对于每个N，若N为2的整数次方输出“y”，否则输出“n” 【样例输入】 2 4 5 【样例输出】 y n 【数据范围】 对于30%的数据，1<=T<=100000 对于50%的数据，1<=T<=1000000 对于100%的数据，1<=T<=5000000，1<=N<=2^64 （为了计算的方便，规定1s做10000000次运算） 【分析】 对于30%的数据，很明显就是一次次的试除。 对于50%的数据，也不难构造算法：预处理出所有2^0~2^64的值，然后二分查找N是否在这64个数中，若在输出y反之输出n。此算法时间复杂度大概6000000左右。 对于100%的数据，上面的算法显然不够用了，此时只能用1重循环解决。 列出所有2的幂次方的二进制表示，可以发现一个规律：都是由1个1打头，后面跟着若干个0（实际上这个规律是可以证明的，为节省篇幅此处不作详细介绍），这也就是说若N是2的幂次方且其2进制表示共有K位（1个1和K-1个0），则N-1的2进制表示共有K-1个1。列一个竖式，我们不难想到使用位运算中的and运算（相同取1，不同取0）。 若N是2的幂次方，则N and (N-1)一定等于0（自己列竖式就可以发现），反正不等于0，于是代码就可以轻而易举的写出来。
#include<iostream> using namespace std; int main() { long long n; int t; cin>>t; while (t--) { cin>>n; if (n & (n-1)) cout<<"N"<<endl; else cout<<"Y"<<endl; } return 0; }转载于:https://www.cnblogs.com/JRX2015U43/p/6533464.html
