【位运算技巧】与运算符(4)二进制中1的个数

【位运算技巧】与运算符(4)二进制中1的个数

一、题目

输入一个整数,输出该数二进制表示中1的个数。例如,9的二进制位1001,有2位1.

二、题解

1.奇巧淫技

1.1 方式一

与运算(最优),我们知道n&(n-1)有消除数组最低位1的效果。

例如,1001 & (1001-1) = 1000。如此往复则可以知道一个二进制数中有多少个1.

    public static int solution(int num) {
        int count = 0;
        while (num != 0) {
            num = num & (num - 1);
            count++;
        }
        return count;
    }
1.2 方式二

num往右移动,每次与1做与&运算,判断是否等于1

    public static int solution1(int num) {
        int count = 0;
        while (num != 0) {
            if ((num & 1) == 1) count++;
            num >>= 1;
        }
        return count;
    }
1.3 方式三

1往左移动,每次和num比对,判断是否不为0(因为int最多32位,所以只循环32次)

    public static int solution2(int num) {
        int count = 0;
        for (int i = 0; i < 32; i++) {
            if ((1 << i & num) != 0) count++;
        }
        return count;
    }

2.其他解法

其他做法,数组转成二进制,再转字符数组判断。

    public static int solution3(int num) {
        char[] chars = Integer.toBinaryString(num).toCharArray();
        int count = 0;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == '1') count++;
        }
        return count;
    }