一. 位运算
- Java int 类型可以直接进行位运算，位运算进行时是换算成二进制运算的，运算完成后的结果也是十进制的 int 类型；
- n & (n-1) 可以去除 n 中最低位的 1；如 0100 & 0011 = 0000
- n & (-n) 可以得到 n 中最低位的 1；（注意负数在计算机中是以补码的形式出现），如 0100 & 1100 = 0100。
1. 基础问题
例题461，汉明距离。两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。给你两个整数 x 和 y，计算并返回它们之间的汉明距离。
- 汉明距离是两个二进制数异或
public int hammingDistance(int x, int y) {
//int类型可以直接异或，异或完以后还是int类型（十进制）
int diff = x ^ y;
//计算diff有几个1
int res = 0;
while(diff > 0) {
//和1相与，判断最后一位是0还是1
res += diff & 1;
//右移去除最低位
diff = diff >> 1;
}
return res;
}
还可直接利用性质——n & (n-1) 可以去除 n 中最低位的 1——进行计算：
public int hammingDistance(int x, int y) {
//int类型可以直接异或，异或完以后还是int类型（十进制）
int diff = x ^ y;
int res = 0;
while(diff > 0) {
res ++;
diff = diff & (diff-1);
}
return res;
}
例题190，颠倒二进制位。颠倒给定的 32 位无符号整数的二进制位。注意数据溢出问题。
- 可以仿照十进制代码翻转的题目进行二进制翻转。但是要考虑溢出的问题，因此采用位运算。
- 另外题目明确说明了是32位数，因此需要循环32次。
public int reverseBits(int n) {
int res = 0;
for (int i = 0; i < 32; i++) {
res = res << 1; //右移一位
res += n & 1; //取n最后一位
n = n >> 1; //n左移一位
}
return res;
}
例题 136，只出现一次的数字。给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
- 使用异或找出只出现一次的元素。利用 x ^ 0 = x，x ^ x = 0 的性质，遍历数组，将所有数进行异或，最后所有相同的数异或为0，0与只出现一次的那个元素异或等于那个元素。
- 说明异或满足交换律，不考虑元素出现的顺序。
public int singleNumber(int[] nums) {
int res = 0;
for (int num : nums) {
res = res ^ num;
}
return res;
}
例题268，丢失的数字。给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
- 只出现一次的数字和丢失的数字都是异或的经典问题。将[0, n] 中所有的数字都异或一次，再与nums数组中的数字都异或一次，则丢失的数字只出现一次，其余数字出现两次，异或之后的结果即是丢失的数字。
- 另一种解法是计算nums的累加和，再利用公式（首项+尾项）* 项数 / 2 减累加和得到结果。
public int missingNumber(int[] nums) {
int res = 0;
int n = nums.length;
for (int i = 0; i <= n; i++) {
res = res ^ i;
}
for (int num : nums) {
res = res ^ num;
}
return res;
}
例题 260。只出现一次的数字2。给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
- 这道题只出现一次的元素有两个，可以想着怎么将其转化为只含一个的题。
- 先将所有数全部异或一遍，取得数的其中为1的一位，在该位两个只出现一次的数必然一个是1，一个是0。其他出现两次的数在该位无论是1还是0都没关系。
- 根据此特性将数组分为两组，则每一组中都只含一个出现一次的元素。再分别进行异或。
public int[] singleNumber(int[] nums) {
//先全部异或一遍
int ans = 0;
for(int num : nums) {
ans = ans ^ num;
}
//取ans的其中为1的一位，在该位两个只出现一次的数必然一个是1，一个是0
//其他出现两次的数在该位无论是1还是0都没关系
//根据此特性将数组分为两组，则每一组中都只含一个出现一次的元素
ans = ans & (-ans); //取最低位为1的
int[] res = new int[2];
for (int num : nums) {
//当前数在该位是1
if ((ans & num) == ans) {
res[0] = res[0] ^ num;
} else {
res[1] = res[1] ^ num;
}
}
return res;
}
2. 二进制特性
例题318，最大单词长度乘积。给你一个字符串数组 words ，找出并返回 length(words[i]) * length(words[j]) 的最大值，并且这两个单词不含有公共字母。如果不存在这样的两个单词，返回 0 。
- 这道题最大的问题是如何快速判断两个单词是否含有相同的字母。
- 可以为每个单词创建一个长度为26的二进制数字，用1表示字母出现，0表示字母未出现。两个单词如果含有相同的字母，则二进制数字相与为0。
public int maxProduct(String[] words) {
int[] arr = new int[words.length];
for (int i = 0; i < words.length; i++) {
char[] word = words[i].toCharArray();
int r = 0;
for (char w : word) {
int t = w - 'a';
r = r | 1 << t; // 将 1 右移 t 位，然后与 t 或
}
arr[i] = r;
}
int res = 0;
for (int i = 0; i < words.length; i++) {
for (int j = i+1; j < words.length; j++) {
if ((arr[i] & arr[j]) == 0) {
res = words[i].length() * words[j].length() > res ? words[i].length() * words[j].length() : res;
}
}
}
return res;
}
例题 338，比特位计数。给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
- 利用 n&(n-1) 可以去除最后一位1的性质计数。
public int[] countBits(int n) {
int[] ret = new int[n+1];
int count = 0;
int tmp = 0;
for (int i = 0; i <= n; i++) {
count = 0;
tmp = i;
while (tmp != 0) {
count ++;
tmp = tmp & (tmp-1);
}
ret[i] = count;
}
return ret;
}
- 动态规划与位运算结合。如果当前数最后一位是1，则1的个数等于它前一个数1的个数+1；如果等于0，则1的个数等于该数右移1位后得到的数的1的个数。
public int[] countBits(int n) {
int[] dp = new int[n+1];
dp[0] = 0;
for (int i = 1; i <= n; i++) {
//如果当前数最后一位是1
if ( (i & 1) == 1) {
dp[i] = dp[i-1] + 1;
} else {
dp[i] = dp[i >> 1];
}
}
return dp;
}
- 还可以将动态规划与 n&(n-1) 的性质结合一下：i & (i-1) 比 i 少一个1，且 i > i & (i-1)
public int[] countBits(int n) {
int[] dp = new int[n+1];
dp[0] = 0;
for (int i = 1; i <= n; i++) {
dp[i] = dp[i & (i-1)] + 1;
}
return dp;
}
例题 693，交替位二进制数。给定一个正整数，检查它的二进制表示是否总是 0、1 交替出现：换句话说，就是二进制表示中相邻两位的数字永不相同。
- 自己写的笨方法，while循环不断获取最后一位，判断最后一位是否不同。
public boolean hasAlternatingBits(int n) {
int t1 = 0;
int t2 = 0;
while (n != 0) {
t1 = n & 1;
n = n >> 1;
t2 = n & 1;
if ((t1 ^ t2) != 1) {
return false;
}
}
return true;
}
- 看题解获得的解法，超帅！如果某数是 0 1 交替出现，那么该数右移一位将得到 1 0 交替出现的数，两者异或必得到全1的数。全1 的数与该数+1 的数相与将得到全零的数。
public boolean hasAlternatingBits(int n) {
int m = n ^ (n >> 1); //如果是交替出现将得到全1的数
return (m & (m + 1)) == 0;
}
例题 476，数字的补数。对整数的二进制表示取反（0 变 1 ，1 变 0）后，再转换为十进制表示，可以得到这个整数的补数。例如，整数 5 的二进制表示是 “101” ，取反后得到 “010” ，再转回十进制表示得到补数 2 。给你一个整数 num ，输出它的补数。
- 关键是如何得到十进制数对应的二进制数的位数，即最高位1是第几位。
- 可不断循环得到位数，再与高一位的数减1（全一）异或，则得到相反数。
public int findComplement(int num) {
int n = num;
int s = 1;
while (n > 0) {
n = n >> 1;
s = s * 2;
}
return num ^ (s -1);
}
