剑指offer-day21

2022年04月27日

后面开始涉及位运算与数学知识了，由于这方面比较薄弱，题目基本都是不会做的，就直接看答案吧，争取把答案看懂就行。

二进制中1的个数

最简单的想法就是把二进制转为字符串，遍历得到1的个数，当然这不是最优解，最优解是对每一位的数和1进行与运算（与运算，即只有在两数都是1时才返回1，其余可能都返回0），当返回值是1，说明该位位数是1，对计算总和+1，否则+0。然后再将二进制数往右移1位，一直移至n的所有位数都为0（即数的十进制为0）即可。（java中，>> 是右移位数的意思，后面跟的值是右移几位的意思，而 >>> 则是右移的同时在缺失的高位补0）。

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int res = 0;
        while(n != 0){// 当n=0时，跳出循环
            res += (n & 1);// res累加n和1进行与运算的结果
            n >>>= 1;// n右移1位，高位补0
        }
        return res;
    }
}

不用加减乘除做加法

题目摆明了要用位运算，最优解是通过观察加法的规律来得出位运算的解决方案。

观察得知，当位数都是0时，它们的和是0，进位是0；当位数有一个是1时，它们的和是1，进位是0；当位数都是1时，它们的和是0，进位是1。可以发现和的计算跟异或运算是一样的（异或运算，即是当两数不相同时，返回值为1，两数相同则返回0），进位的计算跟与运算后是一样的。那么加法可以换算成和与进位的和（其中进位需要左移一位，这样才能体现进位）。

class Solution {
    public int add(int a, int b) {
        while(b != 0) { // 当进位为 0 时跳出
            int c = (a & b) << 1;  // c = 进位
            a ^= b; // a = 非进位和
            b = c; // b = 进位
        }
        return a;
    }
}