剑指offer笔记（11）位运算

「爱情、让人受尽委屈。」 2022-10-10 12:51 122阅读 0赞

![20210628161028309.png][]

二进制中1的个数

最简单的方法就是，依次右移，再与1& 根据&的结果判断是否为1

int NumOf1(int n)
    {
        int count=0;
        while(n)
        {
            if(n&1)
                count++;
            n=n>>1;
        }
        return count;
    }

我们都知道右移一位等价于整数除以2，那么此处是否可以用除法代替呢？

除法效率要比移位运算的效率低得多，一般都通过采用位运算来代替除法运算

但此时又有另外一个问题，如果输入一个负数，比如：0x80000000

0x80000000在右移过程中不仅仅将高位的1逐个右移即可，而且需要考虑符号位，最终将变成0xffffffff，此时再移动将会陷入死循环

对此代码还需要进一步改进：

我们不移动原始数据，而是给一个标志位&原始数据，通过标志位的逐位变化（左移等价于乘2）来判断原始数据中1的个数，这样就保证了原始数据不会被破坏

int NumOf1(int n)
    {
        int count=0;
        unsigned int flag =1
        while(flag)
        {
            if(n&flag)
                count++;
            flag=flag<<1;
        }
        return count;
    }

除上述此种方法，更有思路清奇的做法：

把一个整数减去1，再与原数据与运算，会把原数据最右边一个1变为0，原数据中有多少个1就会进行多少次操作

int NumOf1(int n)
    {
        int count=0;
        while(n)
        {
            count++;
            n=(n-1)&n;
        }
        return count;
    }

[20210628161028309.png]: /images/20221005/ff9b0889129f4581b0afa793ab68d832.png

发表评论取消回复

表情：

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

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

相关阅读

相关剑指offer笔记

面试题3 数组中的查找对于这道题来说，书上的和LeetCode上的是不一样的。在LeetCode上，是一位数组中判断是否有重复数字，有的话任意返回一个就行。这个思路

た入场券/ 2023年07月13日 03:46/ 0 赞/ 48 阅读

相关剑指offer题解——位运算和哈希表

文章目录剑指 Offer 15. 二进制中1的个数解法剑指 Offer 39. 数组中出现次数超过一半的数字

我就是我/ 2023年03月01日 12:30/ 0 赞/ 17 阅读

相关《剑指offer》：位运算的巧用

一、不用加减乘除做加法题目描述：写一个函数，求两个整数之和，要求在函数体内不得使用+、-、\、/四则运算符号。解答思路：使用二进制的方法进行求解。第一步：各位

古城微笑少年丶/ 2023年02月17日 05:30/ 0 赞/ 25 阅读

相关剑指offer笔记（11）位运算

![20210628161028309.png][] 二进制中1的个数最简单的方法就是，依次右移，再与1& 根据&的结果判断是否为1 int NumOf1(in

「爱情、让人受尽委屈。」/ 2022年10月10日 12:51/ 0 赞/ 123 阅读

相关《剑指offer》刷题笔记（位运算）：二进制中1的个数

《剑指offer》刷题笔记（位运算）：二进制中1的个数 -------------------- 转载请注明作者和出处：[http://blog.csdn.net

绝地灬酷狼/ 2022年06月08日 02:24/ 0 赞/ 218 阅读

相关【剑指offer】11-20题

11.给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。不得使用库函数，不需要考虑大数问题思路：不能用==比较两

谁践踏了优雅/ 2022年05月14日 14:57/ 0 赞/ 149 阅读

相关剑指offer-问题11

package offer; / offer interview 11 / public class Test11 {

朴灿烈づ我的快乐病毒、/ 2022年05月10日 14:14/ 0 赞/ 100 阅读

相关【剑指Offer】不用加减乘除做加法（位运算）

题目链接：[https://www.nowcoder.com/practice/59ac416b4b944300b617d4f7f111b215?tpId=13&tqId=11

曾经终败给现在/ 2022年03月16日 13:16/ 0 赞/ 175 阅读

相关【剑指Offer】二进制中1的个数（位运算）

题目链接：[https://www.nowcoder.com/practice/8ee967e43c2c4ec193b040ea7fbb10b8?tpId=13&tqId=11

淩亂°似流年/ 2022年03月15日 05:10/ 0 赞/ 248 阅读

相关剑指offer2.4.3位运算

题目：请实现一个函数，输入一个整数，输出该整二进制表示中1的个数。例如把9表示成2进制是1001，有2位是1。因此如果输入9，该函数输出2. ![在这里插入图片描述][

柔光的暖阳◎/ 2021年09月19日 06:02/ 0 赞/ 214 阅读