Skip to content

Latest commit

 

History

History
83 lines (68 loc) · 3.53 KB

JZ11_二进制中1的个数.md

File metadata and controls

83 lines (68 loc) · 3.53 KB

JZ11_二进制中1的个数

首先需要明白:

正数在计算机中以二进制原码的形式(原码,反码,补码相同)存放,以8位二进制为例,它可表示的数据的范围为-128~127,如127在计算机中以0111 1111的形式存放,对应的-127在计算机中以1000 0001存放

而0的补码表示为0000 0000,特别的-128表示为1000 0000(可以记为0的补码就是+0的补码,而-128的补码就是-0的补码)

本题整数范围为32位,则表示范围位-2^312^31-1,(刚刚说的8位二进制范围对应为-2^72^7-1),注意:32位最高次幂是31次

弄清楚以上的知识点后,给出两个方法

方法1:对于一个正数或0,我们通过短除法(除2取余)的方式获取10进制数对应的二进制数中1的个数,而对于一个负数(不包含-2^31),它是以补码的形式存放的,因此,其中1的个数为32减去该负数对应正数的1的个数,之后如果该负数对应正数的二进制表示的最后一位为1,则1的个数要再+1(因为补码是除符号位外取反+1,如果之前最后一位为1,则取反加1后会多一个1)

最后由于-2^31的补码与正常的计算方式不同,所以直接特殊判断输出1(就像8位二进制存放时,-128的补码为 1000 0000是一样的,也输出1)

public class Solution {
    public int NumberOf1(int n) {
        if (n == -2147483648)
            return 1;
        int ans = 0;
        int cnt = 0;
        //这里flag表示是否需要加上额外的一个1,这种情况只发生在n为负数中
        int flag = 0;
        if (n < 0) {
            n = -n;
            while (n > 0) {
                cnt++;
                if (cnt == 1 && n % 2 == 1) flag = 1;
                ans += n % 2;
                n /= 2;
            }
            return 32 - ans + flag;
        } else {
            while (n > 0) {
                ans += n % 2;
                n /= 2;
            }
            return ans;
        }
    }
}

方法二:二进制位运算

在理解上述原码,反码,补码的概念后,借用二进制位运算可以更直观获得1的个数

如果输入的只是正数,那么可以直接每次右移一位n,看一下最低位是否为1(右移时最高位不断自动补0),但是对于负数,在右移过程中最高为不断自动补1(因为要保证依旧为负数),无法通过计数统计1的个数,所以下面采用一个index初始为1,去代替n移位,从2的0次幂移动到2的32次幂,不断与n进行&操作(由于index中只有一个1,虽然它在逐渐向高位移动),只要n对应位置为1,则&运算的结果!=0,否则必为0,起到了判断对应次幂是否为1的作用

public class Solution {
    public int NumberOf1(int n) {
        int ans = 0;
        //只要index&n不等于0代表n的对应二进制位上时1,计数
        int index = 1;
        while (index != 0) {
            if ((n & index) != 0) ans++;
            //index从2的0次幂逐渐移动1的位置,不断乘2左移一位,去比较n的高次幂上是否为1
            //index的值变化为1、2、4.....2^30、-2^31(因为移动到符号位上了)、0
            index <<= 1;
        }
        return ans;
    }
}

对于上面提到的单纯想获取一个正数二进制中1的个数可以采用下面的方式

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