二进制数1的个数及两二进制数异或后1的个数的奇偶

134 阅读 0 评论 89 点赞

我是靠谱客的博主紧张胡萝卜，这篇文章主要介绍二进制数1的个数及两二进制数异或后1的个数的奇偶，现在分享给大家，希望可以做个参考。

二进制数1的个数

判断二进制数1的个数，通过x &= x-1来不断消掉x的最右面的一位1，通过消除次数判断x的1的个数
例如x=0100,则x-1=0011,(x &= x-1) =0000，所以x中的1的个数为1

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//常规方法判断x的二进制中１的个数
int onescount(int x){
int cnt = 0;
while(x){
cnt++;
x &= x-1;
}
return cnt;
}
//预处理1-len的每个i的二进制数的1的个数
for(int i = 1; i < len; ++i) bits[i]=bits[i^(i&-i)]+1;
//C++内置函数__builtin_popcount(i)求取i的二进制数有多少１
for(int i = 1; i < len; ++i) bits[i]=__builtin_popcount(i);

两个二进制数异或后1的个数的奇偶

假设两个二进制数分别为a,b，长度均为len
a中有x个0，len-x个1
b中有y个0，len-y个1
a^b后1的来源有（0,1），（1,0）这两个异或
假设a中的x个0有k个和b中的1进行异或产生1，那么剩下的x-k个0和b中的0异或
b中的0有x-k个被a中的0异或，剩下的y-x+k个0和a中的1异或产生1

因此a、b异或后产生的1的总数量为 $y - x + 2 k$ ,其中 $2 k$ 为偶数，所以我们只需要判断y-x的奇偶性就可以了。（不需要管y-x的正负，因为可以将2k加到y上面，不会改变y的奇偶性，而整个式子是严格大于等于0的）
那么
奇数-奇数和偶数-偶数都是偶数
奇数-偶数和偶数-奇数都是奇数