算法详解：如何计算二进制中1的个数

算法详解：如何计算二进制中1的个数

在计算机科学领域，理解二进制表示和位运算对于解决各种编程问题至关重要。本文将介绍一个经典算法问题：如何计算一个整数的二进制表示中1的个数。通过这个例子，你将掌握一种高效且优雅的解决方案，并深入了解位运算的巧妙应用。

问题描述

输入一个整数，输出该数32位二进制表示中1的个数。其中负数用补码表示。

数据范围：-2^31 <= n <= 2^31 - 1
即范围为：-2147483648 <= n <= 2147483647

示例1

输入：10
返回值：2
说明：十进制中10的32位二进制表示为0000 0000 0000 0000 0000 0000 0000 1010，其中有两个1

示例2

输入：-1
返回值：32
说明：负数使用补码表示，-1的32位二进制表示为1111 1111 1111 1111 1111 1111 1111 1111，其中32个1

解题思路

关键在于理解位运算n & (n - 1)的作用：它可以将n的位级表示中最低的那一位1设置为0。通过不断执行这个操作，直到n变为0，可以统计出二进制表示中1的个数。这种方法的时间复杂度为O(M)，其中M表示1的个数。

代码实现

public int NumberOf1(int n) {
    int cnt = 0;
    while (n != 0) {
        cnt++;
        n &= (n - 1);
    }
    return cnt;
}

总结

通过位运算n & (n - 1)，我们能够以O(M)的时间复杂度（其中M为二进制表示中1的个数）高效计算一个整数的二进制表示中1的个数。这种方法简洁且快速，尤其适用于处理大范围的整数。通过理解和应用这一技巧，不仅能解决类似的面试问题，还能加深我们对位运算的掌握，提高编程能力。