『题解』CodeForces CF1527A And Then There Were K

仙山有茗 · 2021-12-22 22:33:10 · 题解

题目传送门

题目大意

给定一个正整数 n，求出一个最大的 k，满足 n\&(n-1)\&(n-2)\&...\&(k)=0。

思路

先来手算一下答案是啥。

以 n=15 为例，15 的二进制为 1111。

进行一下操作：

• 1111&(1111-1)=1110；
• 1110&(1111-2)=1100；
• 1100&(1111-3)=1100；
• 1100&(1111-4)=1000；
• 1000&(1111-5)=1000；
• 1000&(1111-6)=1000；
• 1000&(1111-7)=1000；
• 1000&(1111-8)=0000；

到 k=7 时圆满结束。

可以推断出，从 k 到 n 的二进制中，第一位永远不是 0。等到 k-1 时，才会出现第一位是 0 的情况。那么最终的 k 的二进制位数等于 n 的二进制位数减一，那么 \lfloor \log_2n \rfloor 就是 k 的位数，那么 2^{\lfloor \log_2n \rfloor} 就是最小的 n 的位数的数，它减一就是答案 k 了。

最终答案为：2^{\lfloor \log_2n \rfloor}-1，即 (1<<(int)log2(n))-1。

代码

#include <iostream>
#include <cmath>
using namespace std;
int t,n;

int main(){
    cin >> t;
    while(t--){
        cin >> n;
        cout << (1<<(int)log2(n))-1 << endl; // 直接套
    }
    return 0;
}