【剑指offer】二进制中1的个数&&2的幂

👉位运算👈

位运算是把数字将二进制表示之后，对每一位上0或者1的运算。二进制及其位运算是现代计算机学科的基石，很多底层技术都离不开位运算，因此与位运算相关的题目也经常出现在面试中。因为在我们的日常生活中，用得最多的进制就是十进制，所以很多人面对二进制及位运算的题目时多少会有点不适应。但是无需害怕，如果对位运算还不太熟悉的小伙伴，可以先看一下这篇文章：👉操作符详解👈。

👉二进制中1的个数👈

题目：

请实现一个函数，输入一个整数，输出该数二进制表示中1的个数。例如：把9表示成二进制是1001，有2位是1,。因此如果输入9，该函数的返回值为2。

可能引起死循环的解法

这是一道很基本的考查二进制和位运算的面试题，题目不是很难。基本思路：先判断整数二进制表示中最右边一位是不是1，借助把输入的整数右移一位，此时原来处于从右边数起的第二位被移动到最右边了，在判断是不是1.这样每次移动一位，直到整个整数编程0为止。

现在的问题变成了判断一个整数的最右边是不是1。这很简单，只要把整数和1做位与运算看结果是不是1就知道了。1除了最右边的一位之外所有位都是0.如果一个整数和1做位与运算的结果是1，表示该整数最右边一位是1，否则就是0。

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

这个算法好像没有什么问题啊，那么为什么通不过测试呢？原因就是，如果给上面的函数输入一个负数就会陷入死循环了。比如：0x80000000，把负数0x80000000右移一位的时候，并不是简单地把最高位的1移到后一位变成0x40000000，而是0xC0000000.这是以内移位前是个负数，仍然要保证移位后是个负数，因此移位后高位补1。如果一直做右移运算，最终这个数字就会变成0xFFFFFFFF而陷入死循环。

不能我们稍作修改，就能够通过测试了。就是把 hammingWeight 函数的参数类型改成 unsigned int。尽管你把负数传过来，hammingWeight 函数也会把这个数当做无符号整数（正数）。

还有一点需要注意的是：把一个整数右移一位和把一个整数除以2在数学上是等价的，但是除法的效率比移位运算要低很多，在实际编程中华应尽可能地用移位运算符来代替乘除法。

除了上面的解法，还有没有其他解法呢？其实还有，接下来为大家介绍另一种解法。

常规解法

既然，移动输入的数字n有可能造成死循环。那我们可不可以换个方向，换成移动1呢？其实也是可以的。首先把n和1做位与运算，判断n的最低位是不是为1。接着把1左移一位得到2，再和n做位与运算，就能判断n的次低位是不是1。如此反复左移，每次都能判断你的其中一位是不是1，直至1左移变成0。

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

奇妙的解法

在分析这种算法之前，我们先来分析一个数减去1的情况。如果一个整数不等于0，那么该整数的二进制表示至少有一位是1。先假设这个数的最右边一位是1，那么减去1时，最后一位变成0而其它所有位都保持不变。也就是相当于最后一位做了取反操作，由1变成了0。

接下来假设最后一位不是1而是0的情况。如果该整数的二进制表示中最右边的1在第m位，那么减去1时，第m位由1变成0，而第m位之后的所有0都变成1，整数中第m位之前的所有位都保持不变。举个例子：一个二进制数1100，它的第三位是从最右边数起的一个1。减去1后，第三位变成0，它的后面的两位0变成1，而前面的1保持不变，因此得到的结果是1011。

在前面两种情况中，我们可以发现一个整数减去1，都是把最右边的1变成0.如果它的右边还有0的话，所以的0都变成1，而他左边所有位都保持不变。接下来我们把一个整数和它减去1的结果做位与运算，这个操作相当于把它最右边的1变成0.以前面的二进制数1100为例，它减去1的结果是1011.我们再把1100和1011做位与运算，得到的结果是1000。我们把1100最右边的1变成0，结果刚好就是1000。

总结：

把一个整数减去1，再和原整数做位与运算，会把该整数最右边的一个1变成0。那么一个整数的二进制表示中有多少个1，就可以进行多少次这样的操作。

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

👉2的幂👈

给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。

如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。

示例 1：

输入：n = 1

输出：true

解释：2^0 = 1

示例 2：

输入：n = 3

输出：false

提示：

• -2^31 <= n <= 2^31 - 1

思路：一个整数如果是2的整数次方，那么它的二进制表示中有且只有一位是1，而其它所有位都是0。根据前面的分析，把这个整数减去1之后再和它自己做位与运算，这个整数最右边的1就会变成0。我们只需判断该整数的二进制表示中是不是只有一个1就行了。

int count_bit(unsigned long n)
{
    int count = 0;
    while (n)
    {
        count++;
        n = n & (n - 1);
    }
    return count;
}
bool isPowerOfTwo(int n)
{
    if (count_bit(n) == 1)
        return true;
    else
        return false;
}

注意：之所以count_bit函数的是参数是 unsigned long，是因为不将参数设置成 unsigned long不能通过测试。

👉总结👈

本文主要讲解了如何计算二进制中1的个数，然后引出了一种巧妙的方法 n & (n-1) 来计算二进制中1的个数，并借助这种方法来判断一个数是不是2的幂。如果大家觉得有收获的话，可以点个三连支持一下！谢谢大家啦！！！💖💝❣️