剑指 Offer 15. 二进制中1的个数

题目描述

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为 汉明重量).）。输入必须是长度为32的 二进制串 。 
输入：n = 4294967293 (控制台输入 11111111111111111111111111111101，部分语言中 n = -3）
输出：31
解释：输入的二进制串 11111111111111111111111111111101 ***有 31 位为 '1'。
🔗题目链接：https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof

方法一：通过与运算和移位运算

如9的二进制为1001，当前最低位1，则1001&1=0001，计数，1001>>1=0100，右移一位相当于除以2，以此类推
注意：
  1. 判断时要判断 n != 0 而不是 n>0 。 因为是无符号整数，带符号整数最高位是1时为负数。
  2. 要用 n >>> 1 而不是 n >> 1。因为>>是带符号右移，当n为负数时，最高位补1 
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        while(n != 0){
            if((n & 1) == 1){ //与运算判断最低位是否为1
                count++;
            }
            n = n >>> 1; //无符号右移
        }
        return count;
    }
}

方法二：n & (n-1)消除n最右边的1

不断清除n的二进制表示中最右边的1，同时累加计数器，直至n为0，该方法是无视数字符号的
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        while(n != 0){
            //n & (n-1)能够消除n最右边的1
            n = n & (n - 1);
            count++;
        }
        return count;
    }
}

方法三：函数调用 

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        return Integer.bitCount(n);
    }
}

剑指 Offer 65. 不用加减乘除做加法

题目描述

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

🔗题目链接：https://leetcode-cn.com/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof/

思路

通过位运算异或运算求无进位和，(a & b) << 1 求进位，循环运算，直到进位为0

代码实现 

class Solution {
    public int add(int a, int b) {
        while(b != 0){
            int c = (a & b) << 1; //求进位
            a = a ^ b; //异或求非进位和
            b = c; //将进位赋给b
        }
        return a;
    }
}