二进制中 1 的个数

1年前 (2022) 程序员胖胖胖虎阿
216 0 0

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

要解决这道题,必须清楚以下几个知识点:

  • 对于位运算符 &,,当两个位同时为 1 时结果为 1,否则为 0
  • >> 代表有符号右移,>>> 代表无符号右移,<< 代表无符号左移

错误的解法

从 n 的二进制形式的最右边开始判断是不是 1,但如果输入的是一个负数,则会陷入死循环,因为负数右移的话,最高位补的是 1,而本题的最终目的是求 1 的个数,结果就是会有无数个 1

public class Solution {

    // 可能陷入死循环的解法
    public static int NumberOf1_CanNotUse(int n) {
        int count = 0;
        while (n != 0) {
			
            if ((n & 1) == 1) {
                count++;
            }
            //把n的2进制形式往右推一位
            n = n >> 1;
        }
        return count;
    }
}

解法一

用 1 和 n 的每位进行来判断,然后 1 自身再做一次左移

public class Solution {
    public int NumberOf1(int n) {
        int count = 0;
        int flag = 1;
        while(flag != 0) {
        	if((n & flag) != 0) {
        		count++;
        	}
        	flag = flag << 1;
        }
        return count;
    }
}

解法二

分析以下代码,如果一个整数不为 0,那么这个整数至少有一位是 1。如果我们把这个整数减 1,那么原来处在整数最右边的 1 就会变为 0,原来在 1 后面的所有的 0 都会变成 1(如果最右边的 1 后面还有 0 的话)。其余所有位将不会受到影响。

举个例子:一个二进制数 1100,从右边数起第三位是处于最右边的一个 1。减去 1 后,第三位变成 0,它后面的两位 0 变成了 1,而前面的 1 保持不变,因此得到的结果是 1011。我们发现减 1 的结果是把最右边的一个 1 开始的所有位都取反了。这个时候如果我们再把原来的整数和减去 1 之后的结果做与运算,从原来整数最右边一个 1 那一位开始所有位都会变成 0。如 1100 & 1011 = 1000。也就是说,把一个整数减去 1,再和原整数做与运算,会把该整数最右边一个 1 变成 0。那么一个整数的二进制有多少个 1,就可以进行多少次这样的操作。

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

版权声明:程序员胖胖胖虎阿 发表于 2022年11月3日 下午7:32。
转载请注明:二进制中 1 的个数 | 胖虎的工具箱-编程导航

相关文章

暂无评论

暂无评论...