二进制表示中1的个数与异或关系

本文主要讨论一下二进制表示中1的个数和异或的关系，本文各种结论的证明都会省去，方便记忆。

问题：给定两个数a,b，判断a^b在二进制表示下1的个数的奇偶性。

分析：设a在二进制表示下1的个数为x,b在二进制表示下1的个数为y,a中0匹配了b中k个1.（最后一句话可能有误，不过不影响判断奇偶性）.

故结论为：a^b中1的个数为2*k-y+x，可见a^b中1的个数的奇偶性只与x和y有关，观察可得，如果x,y中一奇一偶，那么答案就是奇数。

 

问题强化版：求在1---->n中任选a,b（a!=b），使得a^b在二进制表示下1的个数为奇数，求a,b的配对方案数,a^b与b^a算是一种情况。(n<=1e7)

分析：由上分析可得，我们可以在O(1)的情况下判断a^b在二进制表示下1的个数的奇偶性，那么如何求出a^b在二进制表示下1的个数呢？

首先提供O(log(n))的方法：

    ll tot=0;（long long int）
    while(w){
        if(w&1)++tot;
        w>>=1;    
    }

这种方法是每次判断末尾为1还是0，但是我们得求出每个数字的1的个数，在1e7的范围下，O（nlog(n)）的方法显然不够用，我们需要一种O(1)求个数的方法，我这里提供两种方法（代码参考博客https://www.cnblogs.com/graphics/archive/2010/06/21/1752421.html）：

模板1：

int BitCount4(unsigned int n) 
{ 
    n = (n &0x55555555) + ((n >>1) &0x55555555) ; 
    n = (n &0x33333333) + ((n >>2) &0x33333333) ; 
    n = (n &0x0f0f0f0f) + ((n >>4) &0x0f0f0f0f) ; 
    n = (n &0x00ff00ff) + ((n >>8) &0x00ff00ff) ; 
    n = (n &0x0000ffff) + ((n >>16) &0x0000ffff) ; 

    return n ; 
}

模板2：

int BitCount5(unsigned int n) 
{
    unsigned int tmp = n - ((n >>1) &033333333333) - ((n >>2) &011111111111);
    return ((tmp + (tmp >>3)) &030707070707) %63;
}

感觉都好记，根据个人爱好选一种吧！

回到加强版的题目，现在问题只在于如何枚举a,b,其实我们并不需要枚举a,b，

只需要知道一个在（二进制表示下1的个数为奇数的数）和(1的个数为偶数的数)是可以贡献答案的，奇可以和偶配对，所以我们只需要求出 tot1=奇数数量 和 tot2=偶数数量,贡献即为 tot1*tot2即可。

 

下面给个例题：

洛谷10月月赛2T1链接//这道题...打月赛的时候忘记取模

代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define R register
#define ll long long int 
using namespace std;
ll n,a,b,c,d;
ll ans,x,w,odd,even;
inline ll getx(){
     return (((a*x)%d*x)%d+b*x%d+c)%d;
}
inline ll get1(R ll k){
    R ll tot=k-((k>>1)&033333333333)-((k>>2)&011111111111);
    return ((tot+(tot>>3))&030707070707)%63;
}
int main(){
    scanf("%lld%lld%lld%lld%lld%lld",&n,&a,&b,&c,&d,&x);
    for(R ll i=1;i<=n;++i){
    x=getx();w=get1(x);
    if(w%2==1)++odd;
    else ++even;
    }
    printf("%lld",1LL*odd*even);
    return 0;
}