当前位置: 代码迷 >> 综合 >> 剑指offer之二进制位1的个数
  详细解决方案

剑指offer之二进制位1的个数

热度:7   发布时间:2024-01-16 23:50:38.0

1.求一个整数的二进制表示中有几个1

  • 基础补习:

    左移m<<n,表示m左边n位直接丢弃,同时在右侧补n个0

    右移m>>n,表示右边n位直接丢弃,负数左侧补n个1,正数和无符号数都是左侧补n个0

2.右移解法(错误的)

不断把数字右移1位,和1做&运算,判断最右侧一位是否是1
int NumberOf1(int n)
{int count = 0;while(n){if(n&1)count ++;n = n >> 1; }return n;
}
当输入负数时,右移时,每次左侧补1,死循环

3.左移解法(正确,但不是最优)

int NumberOf1(int n)
{int count = 0;unsigned int flag = 1;while(flag){if(n & flag)count ++;flag = flag << 1;}return count;
}
从右往左,依次检测n的每一位是否是1.flag由于是无符号数,当1移到最高位时,仍然有效(flag条件为true),当越过最高位时,flag全部是0,while循环结束。循环次数取决于整数的二进制位数,如果32位整数,那么循环32次

4.更优解法

  • 分析 整数n减去1,如果最后一位是1,那么最后一位设为0

    如果最后一位不是1,从右向左找,找到第一个1,设为0,然后后续位置取反,想想小学的借位减法。

    比如二进制数1100减去1,从右往左找到第一个1(红色那个),再把红色以及后面的位取反,减法后变为1011,然后1100 & 1011 = 1000刚好损失最后一个1

    总结:整数n减去1,找到从右往左第一个位置是1的位,把这个位置以及右侧按位取反

    那么n & (n-1),每次损失最右侧的一个1

  • 代码

    int NumberOf1(n)
    {
    int count = 0;
    while(n)
    {count ++; //能进入while,至少有个位是1n = n & (n-1);//损失最右侧一个1位
    }
    return count;
    }
    

    这个数有个位是1,循环几次

    5.更多应用

  • 一条语句判断一个整数是不是2的整数次方,由于2的整数次方,二进制只有一个位是1,其他位都是0,n&(n-1)之后结果必定为0

  • 两个整数m,n,求m二进制中多少个位于n不同。二进制位不同,想到异或,先求m和n的异或,mn有几个位不同,异或值就有几个位是1,然后数1的个数

  相关解决方案