方法总结

基本原理

0s 表示一串 0，1s 表示一串 1。

x ^ 0s = x      x & 0s = 0      x | 0s = x
x ^ 1s = ~x     x & 1s = x      x | 1s = 1s
x ^ x = 0       x & x = x       x | x = x

• 利用 x ^ 1s = ~x 的特点，可以将位级表示翻转；利用 x ^ x = 0 的特点，可以将三个数中重复的两个数去除，只留下另一个数。
• 利用 x & 0s = 0 和 x & 1s = x 的特点，可以实现掩码操作。一个数 num 与 mask：00111100 进行位与操作，只保留 num 中与 mask 的 1 部分相对应的位。
• 利用 x | 0s = x 和 x | 1s = 1s 的特点，可以实现设值操作。一个数 num 与 mask：00111100 进行位或操作，将 num 中与 mask 的 1 部分相对应的位都设置为 1。

位与运算技巧：

• n&(n-1) 去除 n 的位级表示中最低的那一位。例如对于二进制表示 10110100，减去 1 得到 10110011，这两个数相与得到 10110000。
• n&(-n) 得到 n 的位级表示中最低的那一位。-n 得到 n 的反码加 1，对于二进制表示 10110100，-n 得到 01001100，相与得到 00000100。
• n-n&(~n+1) 去除 n 的位级表示中最高的那一位。

移位运算：

• >> n 为算术右移，相当于除以 2n；
• >>> n 为无符号右移，左边会补上 0。
• << n 为算术左移，相当于乘以 2n。

mask 计算

要获取 111111111，将 0 取反即可，~0。

要得到只有第 i 位为 1 的 mask，将 1 向左移动 i-1 位即可，1<<(i-1) 。例如 1<<4 得到只有第 5 位为 1 的 mask ：00010000。

要得到 1 到 i 位为 1 的 mask，1<<(i+1)-1 即可，例如将 1<<(4+1)-1 = 00010000-1 = 00001111。

要得到 1 到 i 位为 0 的 mask，只需将 1 到 i 位为 1 的 mask 取反，即 ~(1<<(i+1)-1)。

不用额外变量交换两个整数

a = a ^ b;
b = a ^ b;
a = a ^ b;

Java 中的位操作

static int Integer.bitCount();           // 统计 1 的数量
static int Integer.highestOneBit();      // 获得最高位
static String toBinaryString(int i);     // 转换为二进制表示的字符串

Java 中负数的二进制表示是反码加1

461. 汉明距离

难度：简单

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。

给出两个整数 x 和 y，计算它们之间的汉明距离。

注意：
0 ≤ x, y < 231.

示例:

输入: x = 1, y = 4

输出: 2

解释:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑

上面的箭头指出了对应二进制位不同的位置。

先把 x，y异或，得到的结果对应二进制位不同的位置就是1，相同是0，再用一个掩码从低到高和这个异或结果相与，用计数器记录结果

136. 只出现一次的数字

难度：简单

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

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

示例 2:

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

两个相同的数异或得到的结果是0 ，对所有数进行异或操作，最后的结果就是单独出现的那个数

public int singleNumber(int[] nums) {
    int result = 0;
    for (int i : nums) {
        result ^= i;
    }
    return result;
}

268. 缺失数字

难度：简单

给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。

示例 1:

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

示例 2:

输入: [9,6,4,2,3,5,7,0,1]
输出: 8

说明:
你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?

实际上这题是有 n + 1 个数，但是只有 n 个坑位，要找到n + 1 中多出的那个数。

所以可以把所有的下标和元素异或起来，因为是全部异或起来，所以顺序就不重要了

public int missingNumber (int[] nums) {
    int missing = nums.length;
    for (int i = 0; i < nums.length; i++) {
        missing = missing ^ i ^ nums[i];
    }
    return missing;
}

260. 只出现一次的数字 III

难度：中等

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。

示例 :

输入: [1,2,1,3,2,5]
输出: [3,5]

注意：

1. 结果输出的顺序并不重要，对于上面的例子， [5, 3] 也是正确答案。
2. 你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

使用位运算的方法。

首先遍历一次数组，将每个元素异或，因为相同的元素异或得到的结果是0，所以遍历数组完成所以异或操作后，得到的结果是那两个只出现一次的元素的异或值，记为diff。

n&(-n) 得到 n 的位级表示中最低的那一位

使 diff = diff & (-diff)，得到两个单身元素异或结果的最低位不同值，等会儿就利用这个不同值找到这两个单身元素。

再次遍历数组，将每个元素与新diff异或，结果为0的全部异或到一起，最后就是要找的单身元素的其中一个；结果不为0的全部异或到一起，最后就是要找的另一个单身元素。

public int[] singleNumber(int[] nums) {
    int diff = 0;
    for (int num : nums) {
        diff = diff ^ num;
    }
    diff = diff & (-diff);
    int[] ans = new int[2];
    for (int num : nums) {
        if ((num & diff) == 0)
            ans[0] ^= num;
        else
            ans[1] ^= num;
    }
    return ans;
}

190. 颠倒二进制位

难度：简单

颠倒给定的 32 位无符号整数的二进制位。

示例 1：

输入: 00000010100101000001111010011100
输出: 00111001011110000010100101000000
解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
      因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。

示例 2：

输入：11111111111111111111111111111101
输出：10111111111111111111111111111111
解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293，
      因此返回 3221225471 其二进制表示形式为 10101111110010110010011101101001。

提示：

• 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
• 在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的 示例 2 中，输入表示有符号整数 -3，输出表示有符号整数 -1073741825。

进阶:
如果多次调用这个函数，你将如何优化你的算法？

通过位操作，不断把n 的最低位往 ans 的尾部加，类似于 StringBuilder 的 append。最后得到的结果就是二进制的颠倒。

// you need treat n as an unsigned value
public int reverseBits(int n) {
    int ans = 0;
    for (int i = 0; i < 32; i++) {
        ans <<= 1;
        ans |= (n & 1);
        n >>>= 1;
    }
    return ans;
}

231. 2的幂

难度：简单

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

示例 1:

输入: 1
输出: true
解释: 2^0 = 1

示例 2:

输入: 16
输出: true
解释: 2^4 = 16

示例 3:

输入: 218
输出: false

n&(n-1) 去除 n 的位级表示中最低的那一位

一个数是2的幂的话，它的二级制表示中只会有一个1，把这个唯一的1去掉了，就是0。

public boolean isPowerOfTwo(int n) {
    return n >0 && (n & (n-1)) == 0;
}

342. 4的幂

难度：简单

给定一个整数 (32 位有符号整数)，请编写一个函数来判断它是否是 4 的幂次方。

示例 1:

输入: 16
输出: true

示例 2:

输入: 5
输出: false

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

利用判断2的幂的类似思路，一个数是4的幂的话，它的4级制表示中只能有一个1，这时候就不能用n&(n-1)去最低位了，因为不是2进制。4进制的4的幂的形式为1后面跟若干个0，也可以没有0，那正好可以用正则表达式中的*来处理。

* 表示匹配前面的子表达式零次或多次

public boolean isPowerOfFour(int num) {
    return Integer.toString(num,4).matches("10*");
}

693. 交替位二进制数

难度：简单

给定一个正整数，检查他是否为交替位二进制数：换句话说，就是他的二进制数相邻的两个位数永不相等。

示例 1:

输入: 5
输出: True
解释:
5的二进制数是: 101

示例 2:

输入: 7
输出: False
解释:
7的二进制数是: 111

示例 3:

输入: 11
输出: False
解释:
11的二进制数是: 1011

示例 4:

输入: 10
输出: True
解释:
10的二进制数是: 1010

对于 1010 这种位级表示的数，把它向右移动 1 位得到 101，这两个数每个位都不同，因此异或得到的结果为 1111。

public boolean hasAlternatingBits(int n) {
    int tmp = (n ^ (n >> 1));
    return (tmp & (tmp + 1)) == 0;
}

476. 数字的补数

难度：简单

给定一个正整数，输出它的补数。补数是对该数的二进制表示取反。

注意:

1. 给定的整数保证在32位带符号整数的范围内。
2. 你可以假定二进制数不包含前导零位。

示例 1:

输入: 5
输出: 2
解释: 5的二进制表示为101（没有前导零位），其补数为010。所以你需要输出2。

示例 2:

输入: 1
输出: 0
解释: 1的二进制表示为1（没有前导零位），其补数为0。所以你需要输出0。

对于 00000101，要求补码可以将它与 00000111 进行异或操作。那么问题就转换为求掩码 00000111。

public int findComplement (int num) {
    if (num == 0) return 1;
    int mask = Integer.highestOneBit(num);
    mask = (mask << 1) - 1;
    return num ^ mask;
}

不使用API的方式

public int findComplement(int num) {
    int mask = num;
    mask |= mask >> 1;
    mask |= mask >> 2;
    mask |= mask >> 4;
    mask |= mask >> 8;
    mask |= mask >> 16;
    return (mask ^ num);
}

371. 两整数之和

难度：简单

不使用运算符 + 和 - ，计算两整数 a 、b 之和。

示例 1:

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

示例 2:

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

a ^ b 表示没有考虑进位的情况下两数的和，(a & b) << 1 就是进位。

递归会终止的原因是 (a & b) << 1 最右边会多一个 0，那么继续递归，进位最右边的 0 会慢慢增多，最后进位会变为 0，递归终止。

public int getSum(int a, int b) {
    return b == 0 ? a ^ b : getSum(a ^ b, (a & b) << 1);
}

318. 最大单词长度乘积

难度：中等

给定一个字符串数组 words，找到 length(word[i]) * length(word[j]) 的最大值，并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词，返回 0。

示例 1:

输入: ["abcw","baz","foo","bar","xtfn","abcdef"]
输出: 16 
解释: 这两个单词为 "abcw", "xtfn"。

示例 2:

输入: ["a","ab","abc","d","cd","bcd","abcd"]
输出: 4 
解释: 这两个单词为 "ab", "cd"。

示例 3:

输入: ["a","aa","aaa","aaaa"]
输出: 0 
解释: 不存在这样的两个单词。

本题主要问题是判断两个字符串是否含相同字符，由于字符串只含有小写字符，总共 26 位，因此可以用一个 32 位的整数来存储每个字符是否出现过。

public int maxProduct(String[] words) {
    int n = words.length;
    int[] var = new int[n];
    for (int i = 0; i < n; i++) {
        String word = words[i];
        for (char c : word.toCharArray()) {
            var[i] |= 1 << (c - 'a');
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            if ((var[i] & var[j]) == 0) {
                ans = Math.max(ans, words[i].length() * words[j].length());
            }
        }
    }
    return ans;
}

338. 比特位计数

难度：中等

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

示例 1:

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

示例 2:

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

进阶:

• 给出时间复杂度为O(n*sizeof(integer))的解答非常容易。但你可以在线性时间O(n)内用一趟扫描做到吗？
• 要求算法的空间复杂度为O(n)。
• 你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数（如 C++ 中的 __builtin_popcount）来执行此操作。

根据特性n&(n-1)是n去掉最右边的1，且n&(n-1)<n。所以每个n的1的个数都是n&(n-1)的1的个数+1。

public int[] countBits (int num) {
    int[] ans = new int[num + 1];
    for (int i = 1; i <= num; i++) {
        ans[i] = ans[i & (i - 1)] + 1;
    }
    return ans;
}