在算法竞赛的世界里，时间复杂度往往决定着代码的生死。当遇到“判断一个整数二进制中1的个数是奇数还是偶数”这个问题时，你还在逐位遍历计数吗？今天就给大家分享三种高效解法，尤其是最后一种O(1)时间复杂度的位运算技巧，堪称竞赛“秒杀”神器！
一、 基础遍历法：新手友好的“笨办法”
这是最容易理解的入门解法，核心思路就是逐位检查二进制的每一位，统计1的个数后判断奇偶。
bool hasOddNumberOfOnes(int n) {
int cnt = 0;
while (n != 0) {
cnt += n & 1; // 提取最低位，是1则计数+1
n >>= 1; // 右移一位，检查下一位
}
return cnt % 2 == 1;
}
这种方法的时间复杂度是O(log n)，循环次数等于数字的二进制位数。优点是逻辑简单、容易上手，适合编程新手理解原理；缺点是面对大数时效率偏低，在竞赛中很难应对极限数据。
二、 快速消一法：竞赛高频的优化解法
这是算法竞赛中出镜率极高的优化思路，核心原理是利用 n & (n - 1) 这个神奇的位运算组合，精准消去二进制中最右侧的1。
核心原理
当我们对 n 执行 n & (n - 1) 操作时，会直接消除 n 二进制表示中最右边的那个1。比如 n = 6 （二进制 110 ）， n - 1 = 5 （二进制 101 ），两者按位与的结果是 100 ，最右侧的1被成功消除。
每消除一个1，我们就对计数器加1，直到 n 变为0。此时计数器的值就是1的总个数，再判断奇偶即可。
bool hasOddNumberOfOnes(int n) {
int cnt = 0;
while (n != 0) {
n &= n - 1; // 消去最右侧的1
cnt++;
}
return cnt % 2 == 1;
}
这种方法的时间复杂度是O(k)，其中k是二进制中1的个数。对比基础遍历法，它的循环次数更少——如果一个数的二进制只有1个1，那么只需要循环1次，效率提升非常明显。
三、 位移异或法：O(1)的终极秒杀技巧
这是本文的压轴技巧，也是算法竞赛大神们最爱的“一行流”解法，无需循环，通过分治思想的位运算组合，直接将1的个数奇偶性浓缩到最低位。
核心原理
利用异或运算“相同为0，不同为1”的特性，恰好对应奇偶性相加规则：奇+奇=偶（1^1=0）、奇+偶=奇（1^0=1）、偶+偶=偶（0^0=0）。
通过从大到小的右移异或操作，把二进制数分段合并奇偶性，最终将全局奇偶性浓缩到最低位，再通过 n & 1 提取结果。
bool hasOddNumberOfOnes(int n) {
n ^= n >> 16;
n ^= n >> 8;
n ^= n >> 4;
n ^= n >> 2;
n ^= n >> 1;
return n & 1;
}
这种方法的时间复杂度是O(1)，无论数字多大，都只需要固定次数的位运算操作，是应对大规模数据的最优解。唯一需要注意的是，该方法需要根据整数位数调整右移步数（比如处理64位整数时，需要增加 n ^= n >> 32 这一步）。
四、 三种方法对比总结
方法 时间复杂度 优点 缺点
基础遍历法 O(log n) 逻辑简单，新手友好 大数效率低
快速消一法 O(k) 效率较高，通用性强 仍需循环，依赖1的个数
位移异或法 O(1) 极致高效，竞赛首选 理解门槛高，需适配位数
写在最后
位运算作为算法竞赛的“黑科技”，往往能在关键时刻带来意想不到的效率提升。这三种方法从基础到进阶，层层递进，不仅能解决二进制1的个数奇偶性问题，更能帮助我们理解位运算的核心思想。
希望今天的分享能帮到各位编程爱好者，下次遇到类似问题，不妨试试这些技巧，感受位运算的魅力！
