a = 0011 1100
b = 0000 1101
-----------------
a&b = 0000 1100
a|b = 0011 1101
a^b = 0011 0001
~a = 1100 0011
基本原理
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
如果a、b两个值不相同，则异或^结果为1。如果a、b两个值相同，异或^结果为0。
利用 x ^ 1s = ~x 的特点，可以将一个数的位级表示翻转；利用 x ^ x = 0 的特点，可以将三个数中重复的两个数去除，只留下另一个数。
1^1^2 = 2
利用 x & 0s = 0 和 x & 1s = x 的特点，可以实现掩码操作。一个数 num 与 mask：00111100 进行位与操作，只保留 num 中与 mask 的 1 部分相对应的位。
01011011 &
00111100
--------
00011000
利用 x | 0s = x 和 x | 1s = 1s 的特点，可以实现设值操作。一个数 num 与 mask：00111100 进行位或操作，将 num 中与 mask 的 1 部分相对应的位都设置为 1。
01011011 |
00111100
--------
01111111
位与运算技巧
n&(n-1) 去除 n 的位级表示中最低的那一位 1。例如对于二进制表示 01011011，减去 1 得到 01011010，这两个数相与得到 01011010。
01011011 &
01011010
--------
01011010
n&(-n) 得到 n 的位级表示中最低的那一位 1。-n 得到 n 的反码加 1，也就是 -n=~n+1。例如对于二进制表示 10110100，-n 得到 01001100，相与得到 00000100。
10110100 &
01001100
--------
00000100
n-(n&(-n)) 则可以去除 n 的位级表示中最低的那一位 1，和 n&(n-1) 效果一样。
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<<4)-1 = 00010000-1 = 00001111。
要得到 1 到 i 位为 0 的 mask，只需将 1 到 i 位为 1 的 mask 取反，即 ~((1<<i)-1)。
Java 中的位操作
static int Integer.bitCount(); // 统计 1 的数量
static int Integer.highestOneBit(); // 获得最高位
static String toBinaryString(int i); // 转换为二进制表示的字符串- Hamming Distance (Easy)
Input: x = 1, y = 4
Output: 2
Explanation:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
The above arrows point to positions where the corresponding bits are different.对两个数进行异或操作，位级表示不同的那一位为 1，统计有多少个 1 即可。
public int hammingDistance(int x, int y) {
int z = x ^ y;
int cnt = 0;
while(z != 0) {
if ((z & 1) == 1) cnt++;
z = z >> 1;
}
return cnt;
}使用 z&(z-1) 去除 z 位级表示最低的那一位。
public int hammingDistance(int x, int y) {
int z = x ^ y;
int cnt = 0;
while (z != 0) {
z &= (z - 1);
cnt++;
}
return cnt;
}可以使用 Integer.bitcount() 来统计 1 个的个数。
public int hammingDistance(int x, int y) {
return Integer.bitCount(x ^ y);
}136. Single Number (Easy)
Input: [4,1,2,1,2]
Output: 4两个相同的数异或的结果为 0，对所有数进行异或操作，最后的结果就是单独出现的那个数。
public int singleNumber(int[] nums) {
int ret = 0;
for (int n : nums) ret = ret ^ n;
return ret;
}268. Missing Number (Easy)
Input: [3,0,1]
Output: 2题目描述：数组元素在 0-n 之间，但是有一个数是缺失的，要求找到这个缺失的数。
public int missingNumber(int[] nums) {
int ret = 0;
for (int i = 0; i < nums.length; i++) {
ret = ret ^ i ^ nums[i];
}
return ret ^ nums.length;
}260. Single Number III (Medium)
两个不相等的元素在位级表示上必定会有一位存在不同。
将数组的所有元素异或得到的结果为不存在重复的两个元素异或的结果。
diff &= -diff 得到出 diff 最右侧不为 0 的位，也就是不存在重复的两个元素在位级表示上最右侧不同的那一位，利用这一位就可以将两个元素区分开来。
public int[] singleNumber(int[] nums) {
int diff = 0;
for (int num : nums) diff ^= num;
diff &= -diff; // 得到最右一位
int[] ret = new int[2];
for (int num : nums) {
if ((num & diff) == 0) ret[0] ^= num;
else ret[1] ^= num;
}
return ret;
}190. Reverse Bits (Easy)
public int reverseBits(int n) {
int ret = 0;
for (int i = 0; i < 32; i++) {
ret <<= 1;
ret |= (n & 1);
n >>>= 1;
}
return ret;
}如果该函数需要被调用很多次，可以将 int 拆成 4 个 byte，然后缓存 byte 对应的比特位翻转，最后再拼接起来。
private static Map<Byte, Integer> cache = new HashMap<>();
public int reverseBits(int n) {
int ret = 0;
for (int i = 0; i < 4; i++) {
ret <<= 8;
ret |= reverseByte((byte) (n & 0b11111111));
n >>= 8;
}
return ret;
}
private int reverseByte(byte b) {
if (cache.containsKey(b)) return cache.get(b);
int ret = 0;
byte t = b;
for (int i = 0; i < 8; i++) {
ret <<= 1;
ret |= t & 1;
t >>= 1;
}
cache.put(b, ret);
return ret;
}a = a ^ b;
b = a ^ b;
a = a ^ b;231. Power of Two (Easy)
二进制表示只有一个 1 存在。
public boolean isPowerOfTwo(int n) {
return n > 0 && Integer.bitCount(n) == 1;
}利用 1000 & 0111 == 0 这种性质，得到以下解法：
public boolean isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}342. Power of Four (Easy)
这种数在二进制表示中有且只有一个奇数位为 1，例如 16（10000）。
public boolean isPowerOfFour(int num) {
return num > 0 && (num & (num - 1)) == 0 && (num & 0b01010101010101010101010101010101) != 0;
}也可以使用正则表达式进行匹配。
public boolean isPowerOfFour(int num) {
return Integer.toString(num, 4).matches("10*");
}693. Binary Number with Alternating Bits (Easy)
Input: 10
Output: True
Explanation:
The binary representation of 10 is: 1010.
Input: 11
Output: False
Explanation:
The binary representation of 11 is: 1011.对于 1010 这种位级表示的数，把它向右移动 1 位得到 101，这两个数每个位都不同，因此异或得到的结果为 1111。
public boolean hasAlternatingBits(int n) {
int a = (n ^ (n >> 1));
return (a & (a + 1)) == 0;
}476. Number Complement (Easy)
Input: 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.题目描述：不考虑二进制表示中的首 0 部分。
对于 00000101，要求补码可以将它与 00000111 进行异或操作。那么问题就转换为求掩码 00000111。
public int findComplement(int num) {
if (num == 0) return 1;
int mask = 1 << 30;
while ((num & mask) == 0) mask >>= 1;
mask = (mask << 1) - 1;
return num ^ mask;
}可以利用 Java 的 Integer.highestOneBit() 方法来获得含有首 1 的数。
public int findComplement(int num) {
if (num == 0) return 1;
int mask = Integer.highestOneBit(num);
mask = (mask << 1) - 1;
return num ^ mask;
}对于 10000000 这样的数要扩展成 11111111，可以利用以下方法：
mask |= mask >> 1 11000000
mask |= mask >> 2 11110000
mask |= mask >> 4 11111111public 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. Sum of Two Integers (Easy)
a ^ b 表示没有考虑进位的情况下两数的和，(a & b) << 1 就是进位。
递归会终止的原因是 (a & b) << 1 最右边会多一个 0，那么继续递归，进位最右边的 0 会慢慢增多，最后进位会变为 0，递归终止。
public int getSum(int a, int b) {
return b == 0 ? a : getSum((a ^ b), (a & b) << 1);
}318. Maximum Product of Word Lengths (Medium)
Given ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
Return 16
The two words can be "abcw", "xtfn".题目描述：字符串数组的字符串只含有小写字符。求解字符串数组中两个字符串长度的最大乘积，要求这两个字符串不能含有相同字符。
本题主要问题是判断两个字符串是否含相同字符，由于字符串只含有小写字符，总共 26 位，因此可以用一个 32 位的整数来存储每个字符是否出现过。
public int maxProduct(String[] words) {
int n = words.length;
int[] val = new int[n];
for (int i = 0; i < n; i++) {
for (char c : words[i].toCharArray()) {
val[i] |= 1 << (c - 'a');
}
}
int ret = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if ((val[i] & val[j]) == 0) {
ret = Math.max(ret, words[i].length() * words[j].length());
}
}
}
return ret;
}338. Counting Bits (Medium)
对于数字 6(110)，它可以看成是 4(100) 再加一个 2(10)，因此 dp[i] = dp[i&(i-1)] + 1;
public int[] countBits(int num) {
int[] ret = new int[num + 1];
for(int i = 1; i <= num; i++){
ret[i] = ret[i&(i-1)] + 1;
}
return ret;
}剑指 Offer 56 - I. 数组中数字出现的次数 力扣
找出数组中两个没有重复的数字
方法一：位运算 reduce() 函数会对参数序列中元素进行累积。 函数将一个数据集合（链表，元组等）中的所有数据进行下列操作：用传给 reduce 中的函数 function（有两个参数）先对集合中的第 1、2 个元素进行操作，得到的结果再与第三个数据用 function 函数运算，最后得到一个结果。
如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0。 把a和b分到两组，每组里其它的数都是出现两次的。
如何分组？随便在异或结果中取一位，这位为0的放一组，为1的放另外一组。 因为a、b两个数在异或结果中为1的那位上必然不同。
class Solution:
def singleNumbers(self, nums: List[int]) -> List[int]:
ret = functools.reduce(lambda x, y: x ^ y, nums)#因为重复的数字异或为0，所以全部异或的结果就是两个只出现过一次的数字的异或结果
div = 1
while div & ret == 0:#python3中 位与& 优先级高于 等于== ，先div&ret，再判断是否等于0
div <<= 1#找到异或结果中为1的那一位
a, b = 0, 0
for n in nums:
if n & div:
a ^= n#该位为1的为a组，全部异或在一起
else:
b ^= n#该位为0的为b组，全部异或在一起
return [a, b]方法二：用字典
class Solution:
def singleNumbers(self, nums: List[int]) -> List[int]:
dic = {}
for num in nums:
if num not in dic:
dic[num] = 1
else:
dic[num] += 1
res = []
for key,val in dic.items():
if val == 1:
res.append(key)
return res剑指 Offer 56 - II. 数组中数字出现的次数 II 力扣
方法一：字典
用字典存数和数出现的次数，然后交换字典键值，输出次数为1的。
class Solution:
def singleNumber(self, nums: List[int]) -> int:
dic = {}
for num in nums:
if num not in dic:
dic[num] = 1#一开始没有，所以赋值1（等于0+1）
else:
dic[num] += 1
for key, value in dic.items():#以列表返回可遍历的(键, 值) 元组数组
if value == 1:
return key方法二：遍历统计
class Solution:
def singleNumber(self, nums: List[int]) -> int:
counts = [0] * 32
for num in nums:
for j in range(32):
counts[j] += num & 1#每一位进行计数
num >>= 1#第一位是在最左边，所以从左向右移位（右移！）
res, m = 0, 3
#利用 左移操作 和 或运算，将 counts 数组中各二进位的值恢复到数字 res 上（循环区间是 i∈[0,31] ）。
for i in range(32):
res <<= 1
res |= counts[31 - i] % m#每一位对m求余数,i=0时，counts[31]即在最左边（最高位）的哪一位
if counts[31] % m == 0：
return res
else：
return ~(res ^ 0xffffffff)由于 Python 的存储负数的特殊性，需要先将 0 - 32 位取反（即 res ^ 0xffffffff ），再将所有位取反（即 ~ ）。
两个组合操作实质上是将数字 32 以上位取反， 0 - 32 位不变。
复杂度分析：
时间复杂度 O(N) ： 其中 N 位数组 nums 的长度；遍历数组占用 O(N) ，每轮中的常数个位运算操作占用 O(1) 。
空间复杂度 O(1) ： 数组 counts 长度恒为 32 ，占用常数大小的额外空间。