位运算

1.  二进制中 1 的个数

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

示例 1：

输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
示例 2：

输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
示例 3：

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

作者：Krahets
链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5vk1l3/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

public class Solution {     // you need to treat n as an unsigned value     public int hammingWeight(int n) {         int count = 0;         while(n != 0) {             count++;             n &= n - 1;         }         return count;     } }   2.  数组中数字出现的次数 II

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

示例 1：

输入：nums = [3,4,3,3]
输出：4
示例 2：

输入：nums = [9,1,7,9,7,9,7]
输出：1

作者：Krahets
链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/9hyq1r/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {     public int singleNumber(int[] nums) {         int a = 0;          int b = 0;
        for(int num : nums) {             a = a ^ (num & ~b);             b = b ^ (num & ~a);         }         return a;     } }    

3.不用加减乘除做加法

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

示例:

输入: a = 1, b = 1
输出: 2
 

提示：

a, b 均可能是负数或 0
结果不会溢出 32 位整数

作者：Krahets
链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5vz6d1/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

解题思路：无进位和 与 异或运算 规律相同，进位 和 与运算 规律相同（并需左移一位）。

非进位和：异或运算
进位：与运算+左移一位
?

class Solution {     public int add(int a, int b) {         while(b != 0) {             int c = ( a & b) << 1;             a = a ^ b;             b = c;         }         return a;     } }    

338. 比特位计数
给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

示例 1:

输入: 2
输出: [0,1,1]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/counting-bits
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：主要是 X & (X - 1)可以消掉最后一个1.

class Solution {
    public int[] countBits(int num) {
        int[] target = new int[num + 1];
        target[0] = 0;

        for(int i = 1; i <= num; i++) {
            target[i] = target[i & (i-1)] + 1;            
        }
        return target;
    }
}