老青菜

剑指offer-二进制中1的个数

2017-01-21

题目

输入一个整数(10-10等等),输出该数二进制表示中1的个数。

知识点

我们先来看下进制转换方法和位移运算。

进制转换

正数十进制转二进制:

1. 用十进制整数/2,可以得到一个商和余数。
2. 再用商/2,又会得到一个商和余数。
3. 如此进行,直到商为小于1时为止,最后把余数逆序组合起来。

负数的二进制转换稍微复杂一点:

1. 先求 十进制数绝对值 的 二进制数,即原码。
2. 取 原码 的 反码。
3. 反码+1

10的二进制就是1010,-10的二进制就是0110

位运算

位操作可以提高程序运行效率,减少除法和取模的运算。
左移<<:所有位都向左移动若干位,丢弃最高位,最低位补0。
右移>>:所有的位向右移动若干位,低位移出(舍弃),高位的空位补符号位,即正数补0,负数补1。
位与&:对应位都是1,为1,否则为0。
位或|:对应位有一个1,为1,否则为0。
位异或^:对应位不相同时,为1,否则为0。

分析

这道题考察的是位运算,通常几种思路可能如下:

思路1

依次将整数右移,判断整数最后一位是否为1(&1),如果结果为1,计数累加。
但是输入为负数的话,就会出现死循环,因为负数在右移的过程中,高位补1了。

思路2

1.整数和1(……0000 0001)做与运算,判断最低位是不是为1。
2.1<<1,得到2(……0000 0010),再和整数做与运算,就能判断次低位是不是1。
3.重复步骤2,一般来说,一个int类型4个字节32位,需要循环32次操作。

实现

//思路1:右移的解法,负数会有问题
int getOneCount1(int n) {
    int result = 0;
    while (n) {
        if ((n&1) == 1) {
            result++;
        }
        n=n>>>1;
    }
    return result;
}

//思路2:左移的解法
int getOneCount2(int n) {
    int flag = 1;
    int result = 0;
    while (flag>=1) {
        if ((n&flag) > 0) {
            result++;
        }
        flag = flag<<1;
    }
    return result;
}

添加测试代码:

printf("%d,", getOneCount1(10));
printf("%d,", getOneCount2(10));
printf("%d,", getOneCount2(-10));

//output
2,9,29
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章