@TOC

剑指offer 15 二进制中1的个数 LeetCode 191

请实现一个函数，输入一个整数（以二进制串形式），输出该数二进制表示中1的个数。例如，把9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。

示例 1：

输入： 00000000000000000000000000001011
输出： 3
解释： 输入的二进制串 00000000000000000000000000001011 中，共有三位为 ‘1’。

示例 2：

输入： 00000000000000000000000010000000
输出： 1
解释： 输入的二进制串 00000000000000000000000010000000 中，共有一位为 ‘1’。

示例 3：

输入： 11111111111111111111111111111101
输出： 31
解释： 输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 ‘1’。

提示：

输入必须是长度为 32 的 二进制串 。

注意：本题与主站 191 题相同：https://leetcode-cn.com/problems/number-of-1-bits/

解题思路

n & (n-1) 位运算可以将 n 的位级表示中最低的那一位 1 设置为 0。不断将 1设置为0，直到 n为 0。
时间复杂度： $O(M)$，其中 M 表示 1 的个数。

Java代码

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int res = 0;
        while(n != 0){
            res++;
            n = n & (n-1);
        }
        return res;
    }
}

扩展题1：剑指offer p103,相关题目一 LeetCode 231

231. 2的幂

给定一个整数，编写一个函数来判断它是否是 2 的幂次方。

示例 1:

输入: 1
输出: true
解释: 20 = 1

示例 2:

输入: 16
输出: true
解释: 24 = 16

示例 3:

输入: 218
输出: false

解题思路

不难发现2的幂次方依次为1,2,4,8,16···，二进制表示如下，其实就是将2依次右移几位，即如果一个整数是2的整数次方，那么他的二进制表示中有且只有一位是1，而其他为都是0，那么根据n&(n-1)会将最二进制最右边的1变为0这个性质解题，一个整数如果是2的整数次方，则进行n&(n-1)后，唯一的一个1也会变成0，即n&(n-1)后结果是0，则可以断定n是2的整数次幂。

Java代码

class Solution {
    public boolean isPowerOfTwo(int n) {
        if(n <= 0) return false;//2的整数次幂一定是正数
        return (n & n-1) == 0;
    }
}

扩展题2：LeetCode342 4的幂

342. 4的幂

给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 4 的幂次方需满足：存在整数 x 使得 n == 4x

示例 1：

输入： n = 16
输出： true

示例 2：

输入： n = 5
输出： false

示例 3：

输入： n = 1
输出： true

提示：

$-2^{31} <= n <= 2^{31} - 1$

进阶：

你能不使用循环或者递归来完成本题吗？

解题思路

如果数字为 4 的幂 $x = 4^a$，则 $a = \log_4 x = \frac{1}{2}\log_2 x$应为整数，那么我们检查 $\log_2 x$是否为偶数就能判断 x 是否为 4 的幂。

Java代码

class Solution {
  public boolean isPowerOfFour(int num) {
    return (num > 0) && (Math.log(num) / Math.log(2) % 2 == 0);
  }
}

​
## 扩展题3 LeetCode面试题05.06 整数转换

面试题 05.06. 整数转换

整数转换。编写一个函数，确定需要改变几个位才能将整数A转成整数B。

示例1:

输入： A = 29 （或者0b11101）, B = 15（或者0b01111）
输出： 2

示例2:

输入： A = 1，B = 2
输出： 2

提示:

A，B范围在[-2147483648, 2147483647]之间

### 解题思路:

我们可以分为两步解决这个问题：第一步求这两个数的异或，第二步统计异或结果中1的位数。

比如10的二进制数表示为1010,13的二进制数表示为1101，异或之后为0111，即10和13是有三位是不同的，也即需要改变1010中的3位才能得到1101。

Java代码

class Solution {
    public int convertInteger(int A, int B) {
        /*根据异或的性质，不同则为1，故异或之后，我们判断异或的结果有多少位1即可，
        判断一个二进制数中有多少位1，又用到了n & (n - 1)可以将二进制n最右边的1变为0这条性质*/

        int C = A^B;
        int count = 0;
        while(C != 0){
            count++;
            C = C & (C - 1);
        }
        return count;
    }
}

举一反三

可见上面的题目基本都用到了n&(n-1)可以将二进制n最右边的1变为0这条性质,很多二进制的问题都可以用这种思路解决，故遇到二进制的问题，应该优先考虑这条性质。