剑指offer笔记——面试题15：二进制中1的个数

• 问题描述
• 代码
• 运行结果
• 相关题目

问题描述

请实现一个函数，输入一个整数，输出该数二进制表示中1的个数。

代码

#include <iostream>

/**
 * 求一个整数的二进制中1的个数
 * 常规解法，循环的次数等于整数二进制的位数，32位的整数需要循环32次
 */
int NumberOf1_1(int n)
{
    int count = 0;
    unsigned int flag = 1;
/*
    起初看书的时候我还以为会陷入死循环，运行时发现flag增加到2147483648后再次左移会变成0从而结束循环
    这是我对数据类型的知识了解不够
    虽然不会陷入死循环，但这样无论几位的数也要循环32次，因此可以先对变量n的位数先做一个判断
    int digitCount = 0;
    for(int m = n; m != 0; m = m >> 1,digitCount++)
        ;
    但是这样的方法不能用于负数，因此程序还是使用书中的写法
*/
    for(; flag;)
    {
        if(n & flag)
            count++;
        flag = flag << 1;
    }
    return count;
}
/**
 * 求一个整数的二进制中1的个数
 * 能给面试官带来惊喜的解法，循环的次数等于整数的二进制中1的个数
 */
int NumberOf1_2(int n)
{
    int count = 0;
    for(; n;)
    {
        count++;
        n = (n - 1) & n;    // 这样计算的效果是，把整数的二进制中，最右边的1，变成0
    }
    return count;
}
int main()
{
    std::cout << NumberOf1_1(9) << std::endl;
    std::cout << NumberOf1_2(9) << std::endl;
    std::cout << NumberOf1_1(-9) << std::endl;
    std::cout << NumberOf1_2(-9) << std::endl;
    std::cout << NumberOf1_1(0) << std::endl;
    std::cout << NumberOf1_2(0) << std::endl;
    return 0;
}

           

运行结果

相关题目

• 用一条语句判断一个整数是不是2的整数次方。

一个整数如果是2的整数次方，那么它的二进制表示中有且只有一位是1，而其他所有位都是0。根据前面的分析，把这个整数减去1之后再和它自己做与运算，这个整数中唯一的1就会变成0

• 输入两个整数m和n，计算需要改变m的二进制表示中的多少位才能得到n。比如10的二进制表示为1010，13的二进制表示为1101，需要改变1010中的3位才能得到1101

我们可以分为两步解决这个问题：第一步求这两个数的异或；第二步统计异或结果中1的位数