位运算

两道位运算题目

1. And Then There Were K (opens new window)

1.1 题目描述

Given an integer nn, find the maximum value of integer kk such that the following condition holds:

​ n & (n−1) & (n−2) & (n−3) & ... (k) = 00

where & denotes the bitwise AND operation. (opens new window)

1.2 思路

​ 进行与运算过程中，只要有一位出现0，那么这一位的最终结果即为0，对于整数n，设其最高位代表2^x ，则如果要让n的最高位为0，则最接近n且能让n的最高位为0的数为：2^x - 1。

​ 如果要证明 k = 2^x - 1即为最终答案，我们需要证明在n ... k 之间的数，使n的其他位为0，考虑2 ^ x,其最高位和n都为1，但2^x其他位都为0，且2^x > k，k即为答案。

1.3 代码

#include <iostream>
using namespace std;
int main()
{
    int t, n;
    cin >> t;
    int x;
    while(t --)
    {
        cin >> x;
        int a = 0;
        int idx = 0;
        while(x)
        {
            if((x&1) == 1) a = idx;
            idx ++;
            x >>= 1;
        }
        cout << (1 << a) - 1 << endl;

    }
}

2.XOR Mixup (opens new window)

2.1 题目描述

​ There is an array aa with n−1 integers. Let xx be the bitwise XOR (opens new window) of all elements of the array. The number x is added to the end of the array a (now it has length nn), and then the elements are shuffled.

​ You are given the newly formed array aa. What is xx? If there are multiple possible values of x, you can output any of them.

2.2 思路

​ 已知 x = a1 ^ a2 ^ a3 ... ^ an - 1 证明： a1 = x ^ a2 ^ ... ^an-1。

>a1 = x ^ a2 ^ ... ^ an-1
>
>​    = (a1 ^ a2 ^ ... ^ an-1) ^a2 ^ a3 ... a^n-1
>
>​	= a1 (a2到an-1都有2个，异或结果为0，0和a1异或为a1)

类似，a中任何一个元素都可以类似证明。即任何一个数都可以作为x。

更一般的，如果一个序列的异或结果为0，那么这个序列的任何一个值都是其他元素的异或结果。

2.3 代码

#include <iostream>
using namespace std;

int main()
{
    int t;
    cin >> t;
    while(t --)
    {
        int n;
        cin >> n;
        int res;
        while(n --)
            cin >> res;
        cout << res << '\n';
    }
}