異或 The Great XOR - HackerRank - the-great-xor 題解

題目描述；

給一個數x，問存在多少個a 滿足 a ^ x > x 且 0 < a < x (^為異或)

重點内容

神他媽規律

解法一

打表（一定找較小的數，大數的話會看不出來）

99

1

10

5

100

27

1000

23

500

11

240

15

由表可以看出，跑2的倍數剛好大與n時，得到的數正好為n與答案的和+1，由此得出解法一

#include <iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<vector>
#include<cstdlib>
using namespace std;

int main()
{
    long long n,sum,kk;
    int t;
    cin>>t;
    //cout<<endl;
    while(t--)
    {
        cin>>n;
        sum = ;
        for(int i=;sum<n+;i++)
        {
            sum*=;
        }
        cout<<sum--n<<endl;
        //cout<<endl;
    }
    return ;
}
           

解法2：比較正常的想法

想一下n的二進制位表示，當n的第i位為0時，此時它的低位無論是0，1都是沒有影響的，故對于每一個第i位為0，對于答案的貢獻是2^i,求和即可

注意：資料類型一定要統一，保險起見都用 Long long

#include <iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<vector>
#include<cstdlib>
using namespace std;

int main()
{
    long long n,sum,kk;
    int t;
    cin>>t;
    //cout<<endl;
    while(t--)
    {
        cin>>n;
        sum = ;
        long long xx = ;
        while(n)
        {
            if(n%==)
                sum+=xx;
            xx*=;
            n/=;
        }
        cout<<sum<<endl;
        //cout<<endl;
    }
    return ;
}