C++各类题目

算法

位运算

快速判断二进制编码中“1”有奇数个还是偶数个

1
2
3
4
5
6
7
8
int odd_ones(unsigned x) {
	x = x ^ (x >> 16);  
    x = x ^ (x >> 8); 
    x = x ^ (x >> 4);  
    x = x ^ (x >> 2);  
    x = x ^ (x >> 1);  
    return x & 1;  
}

对于二进制数1101，判断1数量奇偶的最基本的方法是逐个按位异或，也就是1^1^0^1，这里异或与加法（不进位）类似；

现在考虑优化的办法，思想类似于二分；

1
2
3
4
int x=1101
x^=(x>>2);
x^=(x>>1);
int result=x&1;

x^=(x>>2) 相当于折半；1101^0011=1110 此时最后两位10相当于前者保存了第二位+第四位，后者保留了第一位+第三位的结果；最后这两个异或就是最终结果也就是代码倒数第二行的部分；

int一共32位，思想类似；