A. And Then There Were K

21
五月
2021

发现自己真的好久没有写题解,刚好今天有一个比较水的题让我做的还是蛮感慨的。

题目:

Given an integer n, find the maximum value of integer k such that the following condition holds:

n & (n−1) & (n−2) & (n−3) & … (k) = 0
where & denotes the bitwise AND operation.
Input
The first line contains a single integer t (1≤t≤3⋅104). Then t test cases follow.

The first line of each test case contains a single integer n (1≤n≤109).

Output
For each test case, output a single integer — the required integer k.

题意:

这个题的大体意思就是通过这个位运算符,实现上边的那个式子,输出让那个式子等于0的最后一个数是那个。
当看着这个题的时候,我就觉得这个位运算符,只要出这种二进制的东西我就做不出来。没看懂题就自己害怕了,就没有仔细的想,就胡乱写了几行代码提交了,结果超时……其实这个关于二进制的运算符之前也整理过,或许是因为没怎么接触过这样的题吧,就会觉得题做不出来。但是这个题想一想还是挺简单的

思路:

这个题首先把十进制换成二进制,之后,你可以观察,其实你会发现这个数字到0之前太会慢慢的减少,最后会到达一个1000……的情况,到了这种情况之后下一个数就是0111……这两个数做 **”与”**运算后就是0。所以这个0111……就是我们要找的这个数。
最后在求出这个数的10进制数输出即可。

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
    int t;
    cin>>t;
 
    while(t--)
    {
        long long n;
        cin>>n;
        long long ant=0;
        long long y=n;
        while(y!=0)
        {
            y/=2;
            ant++;
        }
        ant-=1;
        long long l=pow(2,ant);
        cout<<l-1<<endl;
    }
    return 0;
}
TAG

网友评论

共有访客发表了评论
请登录后再发布评论,和谐社会,请文明发言,谢谢合作! 立即登录 注册会员