[剑指 Offer 第 2 版第 15 题] “二进制中1的个数”做题记录

第 15 题：二进制中 1 的个数

传送门：二进制中 1 的个数，牛客网 online judge 地址。

输入一个 32 位整数，输出该数二进制表示中1的个数。

注意：

• 负数在计算机中用其绝对值的补码来表示。

样例1：

输入：9 输出：2 解释：9 的二进制表示是 1001，一共有 2 个 1 。

样例2：

输入：-2 输出：31 解释：-2 在计算机里会被表示成 11111111111111111111111111111110，一共有 31 个 1 。

知识点：1、什么是补码？补码就是一个数与另一个数相加，是一个进制表示下很整的数；

2、正数的补码就是它自己，负数在计算机中的表示是它的补码；

3、数分为：“有符号整数”与“无符号整数”。

记住：1、n & (n - 1) 把最低位的 1 变成 0。

2、Python 中的二进制有陷阱，参考资料：https://www.cnblogs.com/klchang/p/8017627.html。

笔记：

分析：位运算的问题，看答案做出来的，记住 n & (n-1) 能够消掉最低位的 1 即可。

Python 代码1：一位一位算就可以了，注意，做 32 次就可以了。

  class Solution(object):
        def NumberOf1(self, n):
            """
            :type n: int
            :rtype: int
            """
            ans = 0
            for i in range(32):
                if n & 1:
                    ans += 1
                n = n >> 1

            return ans

Python 代码2：Python 中的数是长整型，因此一开始做的时候，要把高于 32 位的全部砍掉

  class Solution(object):
        def NumberOf1(self, n):
            """
            :type n: int
            :rtype: int
            """
            # print((-1 & (2**31-1)) >> 1)
            # print((-3) >> 1)
            n = n & (2 ** 32 - 1)
            # print(n)
            count = 0
            while n != 0:
                if n & 1 == 1:
                    count += 1
                n = n >> 1
                # print(n)
            return count

Python 代码：以下写法等价

  class Solution(object):
        def NumberOf1(self,n):
            """
            :type n: int
            :rtype: int
            """
            counter  = 0

            # Python 中的 32 位整数没有溢出这回事，所以要强行变成 32 位
            # 这一步相当于把这个数变成无符号整数，为了通过 judge 才这么做的

            n = n & 0xFFFFFFFF

            while n:
                n = n &(n-1)
                counter +=1
            return counter

C++ 写法：转成无符号数。

• Java 写法

思路1：

• 熟悉位运算是关键。
• 负数左移的时候，最高位补 1，因此，为了避免死循环，先要把最高位变成 0。

Java 代码：

  public class Solution {
        public int NumberOf1(int n) {
            int count = 0;
            // 负数右移的时候，最高位补 1，因此，为了避免死循环，先要把最高位变成 0
            // 负数右移的时候，最高位补 1，因此，为了避免死循环，先要把最高位变成 0
            // 负数右移的时候，最高位补 1，因此，为了避免死循环，先要把最高位变成 0

            // 为负数的时候，将最高位的 1 变成 0
            // 即由负数变成正数，然后再计算 1 的个数
            if (n < 0) {
                n = n & Integer.MAX_VALUE;
                count++;
            }

            // 当 n 是正数的时候，计算 1 的个数
            while (n != 0) {
                count += n & 1;
                n = n >> 1;
            }
            return count;
        }
    }

思路2：

• 可以使用 1001 作为测试用例来理解，a&(a-1) 的结果会将 a 最右边的 1 变为 0 ，直到 a = 0，还可以先将 a&1 != 0,然后右移 1 位，但不能计算负数的值。

Java 代码：

  public class Solution2 {
        public int NumberOf1(int n) {
            int count = 0;
            while (n != 0) {
                count++;
                n = (n - 1) & n;
            }
            return count;
        }
    }

作者：liweiwei1419

来源：https://liweiwei1419.github.io/sword-for-offer/