HDOJ6950 MOD, Or and Everything【位运算】

题目链接：HDU6950

题意

给定一个整数 ，你需要计算 的值。

题解

观察后半段是递减的一个序列，对答案有贡献；前半段不用考虑。

设 ​​​​，对于 ​​​， 结果分别为 ​、、……、、。

再做按位或运算，得到的结果一定每位为 ，即 ​，其中 ​。

注意最后结果非负。

技巧1

如果 ，则答案为 。

技巧2

若 n & (-n) 和 n 相等，则 是 。

技巧3

n -= (n&(-n)) 可快速移除最后一个 。

参考代码

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>

using namespace std;

long long n;

int main() {
    int t; cin >> t;
    while (t--) {
        cin >> n;
        if ((n&(-n)) == n) {
            cout << max(0LL, n/2-1) << endl;
            continue;
        }
        while ((n&(-n)) != n) n -= (n&(-n));
        cout << n-1 << endl;
    }
	
    return 0;
}

复杂度分析

  • 时间复杂度：，其中 是 的位数，可以认为是 的。
  • 空间复杂度：