剑指offer_面试题10_二进制中1的个数（位运算）

秒速五厘米 2022-08-03 08:29 118阅读 0赞

**题目：**请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如把 9 表示成二进制 1001，有 2 个 1。因此如果输入9，该函数输出2。

位运算基本概念：

**五种位运算：与（&）、或（|）、异或、左移 和 右移。**

ps：其中 **异或（运算符 ^）**，1 ^ 0 = 1; 1 ^ 1 = 0; 0 ^ 0 = 0; 0 ^ 1 = 1; 即 相同为假，不同为真。

**左移运算符 <<，**m << n，表示将 m 向左移动 n 位，并且 最左边的 n 位被丢弃，同时最右边补上 n 个 0。比如

00001010 << 2 = **001010** 00； **// 最左边两位被丢弃，最右边两位 补 0；**

10001010 << 3 = **01010** 000；

**右移运算符 >>，**m >> n，表示将 m 向右移动 n 位，并且 最右边的 n 位被丢弃。但最左边的补植比较复杂，分补0 和 补1，比如

00001010 >> 2 = 00 **000010**；  **// 无符号数，最右边两位被舍弃，最左边两位 补0；**

10001010 >> 3 = 111 **10001**；  **// 有符号数，最高位为1，表示是负数，因此 最右边三位被舍弃，最左边三位 补1；**

**常规解法：（不要用 右移运算来求解，因为若是 有符号数，会补1）**

/*关键值flag，通过左移运算来求解，多少位循环多少次*/
    int Numberof1(int n)
    {
        int count = 0;
        unsigned int flag = 1;
        while(flag)
        { 
            if(n & flag)     /** 0000 0001 ==> 0000 0010 ==> 0000 0100 ==> ...通过值 1 的那一位的移动（并且进行与运算）来判断 n 中 1 的个数 */
                count++;
            flag = flag << 1;
        }
        return count;
    }

**惊喜解法：**

**将一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0。**

/** n & (n - 1) 操作会将 n 最右边的一个 1 变为0，可以通过举例来理解*/
    int Numberof2(int n)
    {
        int count = 0;
        while(n)
        {
            count++;
            n = n & (n - 1);
        }
        return count;
    }

**相关题目：**

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

答：若一个数是 2 的整数次方，那其二进制表示中，有且只有一位是 1。使用 n&(n-1)

2、输入两个整数 m 和 n，计算需要改变 m 的二进制表示中的多少位才能得到 n。

答：举例，使用 异或运算，统计异或结果中 1 的个数。

/\*点滴积累，我的一小步O(∩\_∩)O~\*/

发表评论取消回复

表情：

评论列表（有 0 条评论，118人围观）

还没有评论，来说两句吧...

相关阅读

相关【剑指offer】面试题15 - 二进制中 1 的个数

文章目录面试题15：二进制中 1 的个数解法一：移动标志位解法二：移动数本身面试题15：二进制中 1 的个数题目描述：

谁借莪１个温暖的怀抱￠/ 2022年11月06日 07:53/ 0 赞/ 98 阅读

相关剑指offer之面试题10二进制中1的个数

问题描述：请实现一个函数，输入一个整数，输出该数二进制表示1的个数。例如：把9表示成二进制1001，有2位是1。因此如果输入9，该函数输出2. 实现代码如下：

悠悠/ 2022年08月22日 03:45/ 0 赞/ 128 阅读

相关剑指offer面试题二进制中1的个数

题目描述：请实现一个函数，输入一个整数，输出该数二进制中1的个数。例如把9表示成二进制是1001,有2位是1。因此如果输入9，该函数输出2。解法一：常规解法 ![Ce

以你之姓@/ 2022年08月21日 06:56/ 0 赞/ 125 阅读

相关剑指offer_面试题10_二进制中1的个数（位运算）

题目：请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如把 9 表示成二进制 1001，有 2 个 1。因此如果输入9，该函数输出2。位运算基本概念：

秒速五厘米/ 2022年08月03日 08:29/ 0 赞/ 119 阅读

相关剑指Offer面试题10（Java版）：二进制中的1的个数

题目：请实现一个函数，输入一个整数，输出该数二进制表示中1的个数。例如把9表示成二进制是1001，有2位是1，因此如果输入9，该函数输出2. 1、可能引起死循环的解法这是

ゝ一世哀愁。/ 2022年07月16日 04:53/ 0 赞/ 115 阅读

相关剑指offer面试题[10]-二进制中1的个数

题目描述输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。分析：这是一道很基本的考察二进制和位运算的面试题。思路：先判断证书二进制

àì夳堔傛蜴生んèń/ 2022年06月13日 00:21/ 0 赞/ 122 阅读

相关【剑指offer】面试题15：二进制中1的个数

完整代码地址 [完整代码地址][Link 1] 题目请实现一个函数，输入一个整数，输出该数二进制表示中1的个数，其中负数用补码表示。例如，把9表示成二进制是10

客官°小女子只卖身不卖艺/ 2022年06月12日 08:22/ 0 赞/ 135 阅读

相关剑指Offer面试题10：二进制中1的个数

题目描述：请实现一个函数，输入一个整数，输入该数二进制表示中1的个数。例如：把9表示成二进制是1001，有2位是1，所以输入9，该函数输出2 > 可能引起死循环的解法

秒速五厘米/ 2022年05月30日 08:10/ 0 赞/ 151 阅读

相关剑指offer-题10：二进制中1的个数

题目描述输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。例如把9表示成二进制是1001，有2位是1。因此如果输入9，改函数输出2。实验平台：[牛客

﹏ヽ暗。殇╰゛Y/ 2022年05月30日 06:06/ 0 赞/ 111 阅读

相关【剑指offer】面试题15：二进制中 1 的个数

> 题目：请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如把9表示成二进制是1001，有2位是1，因此如果输入9，该函数输出2。 1、可能引起死

左手的ㄟ右手/ 2022年04月10日 10:42/ 0 赞/ 140 阅读