1.汉明距离（461-easy）
题目描述：两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。给出两个整数 x 和 y，计算汉明距离。
示例：
输入: x = 1, y = 4 输出: 2 解释: 1 (0 0 0 1) 4 (0 1 0 0) ↑ ↑
思路：本题寻找位级不同的数目。对两个数进行异或运算（位级不同的元素异或为1），统计出现1的个数。
另外还有两个技巧：z & (z-1) ：把z的二进制表示从低位开始，将遇到的第一个为1的比特位 置0 或者 直接使用库函数统计整数中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 从低位开始的第一个1** public int hammingDistance(int x, int y) { int z = x ^ y; int cnt = 0; while (z != 0) { z &= (z - 1); cnt++; } return cnt; }
//**直接使用库函数统计整数中1的个数。** public int hammingDistance(int x, int y) { return Integer.bitCount(x ^ y); }
2.只出现一次的数字（136-easy）
题目描述：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例：
输入: [4,1,2,1,2] 输出: 4
思路：要求：时间复杂度≤O(n)，额外空间复杂度O(1)。
由于两个相同的数异或的结果为 0，对所有数进行异或操作，最后的结果就是单独出现的那个数（异或运算满足交换率）。
除此之外本题还可以使用，hashset，hashmap，排序等，但不符合题目要求。
代码：位运算
public int singleNumber(int[] nums) { int ret = 0; for (int num : nums) { ret ^= num; } return ret; }
public int singleNumber(int[] nums) { HashSet<Integer> set = new HashSet<>(); for (int num : nums) { if (!set.contains(num)) { set.add(num); } else { set.remove(num); } } return set.iterator().next(); }
3.只出现一次的数字III（260-medium）
题目描述：给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。要求：应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？
示例：
输入: [1,2,1,3,2,5] 输出: [3,5] ps:[5,3]也可
思路：本题的位运算关键是如何将两个不同元素的异或结果进行分离，两个不同的元素至少有一个位级不同。
技巧：xor &= -xor 得到出 xor 最右侧不为 0 的位，这可能来自两个元素的其中一个，所以我们重新遍历数组，用这个位来区分两个不同的数！
代码：
public int[] singleNumber(int[] nums) { int[] ans = new int[2]; int xor = 0; for (int num : nums) { xor ^= num; } // 获取两个数异或后二进制中最低非0位(即区分两个数) xor &= -xor; // 遍历数组与xor进行与操作，即把问题降维到136题 for (int num : nums) { if ((num & xor) == 0) { ans[0] ^= num; } else { ans[1] ^= num; } } return ans; }
4.丢失的数字（268-easy）
题目描述：给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那一个数。
进阶：你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?
示例：
输入：nums = [3,0,1] 输出：2 解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。 输入：nums = [0,1] 输出：2 解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。
思路：注意要求：时间复杂度≤O(n)，额外空间复杂度O(1)。
1.位（xor）运算：异或满足结合律，两个相同的数异或为0，任何数和0异或都为本身；根据上述三点遍历数组，得到缺失值。
2.数学：利用高斯求和公式求出0-n的和，减去数组中所有数的和，就是缺失数字。
ps：hash表和排序也可以解决此问题
代码1：xor运算
public int missingNumber(int[] nums) { int ret = nums.length; for (int i = 0; i < nums.length; i++) { ret ^= i ^ nums[i]; } return ret; }
代码2：数学
public int missingNumber(int[] nums) { //高斯和 int eSum = (nums.length + 1) * nums.length / 2; int aSum = 0; //实际和 for (int num : nums) aSum += num; return eSum - aSum; }
5.颠倒二进制位（190-easy）
题目描述：颠倒给定的 32 位无符号整数的二进制位。进阶:如果多次调用这个函数，你将如何优化你的算法？
示例：
输入: 00000010100101000001111010011100 输出: 00111001011110000010100101000000 解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596， 因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。
思路：
1.移位反转：将n和结果进行移位运算，从右向左依次获取n的二进制数，计入结果集。这里补充一下：无符号右移（逻辑右移）>>>，高位补0，不考虑符号位；有符号右移>>，最高位补原最高位的值，考虑符号位。
2.分治思想+或、与运算：进一步的我们反转可以用分治的思想解决。比如 1 2 3 4，同样的我们只需要交换两部分 1 2 和3 4 的数字，变成 3 4 1 2，接下来只需要分别将两部分 3 4 和 1 2分别逆序，以此类推，八位数字，十六位数字......
ps：二进制中交换两部分，可以用一个技巧，举个例子，对于 x = 1101 交换两部分，我们只需要(1100) & x >>> 2 | (0011) & x <<< 2 = (0011)|(0100)= 0111 ，然后就完成了 11 和 01 的交换。
代码1：移位反转
public int reverseBits(int n) { int ret = 0; for (int i = 0; i < 32; i++) { ret <<= 1; ret |= (n & 1); n >>>= 1; } return ret; }
代码2：分治思想+或、与运算（优化）
public int reverseBits(int n) { //1位十六进制等于4位二进制 n = ((n & 0xffff0000) >>> 16) | ((n & 0x0000ffff) << 16); n = ((n & 0xff00ff00) >>> 8) | ((n & 0x00ff00ff) << 8); n = ((n & 0xf0f0f0f0) >>> 4) | ((n & 0x0f0f0f0f) << 4); n = ((n & 0xcccccccc) >>> 2) | ((n & 0x33333333) << 2); n = ((n & 0xaaaaaaaa) >>> 1) | ((n & 0x55555555) << 1); return n; // ps:jdk源码中也是使用的分治+位运算 //return Integer.reverse(n); }
6.2的幂（231-easy）
题目描述：给定一个整数，编写一个函数来判断它是否是 2 的幂次方。
示例：
输入: 1 输出: true 解释: 20 = 1 输入: 218 输出: false
思路：可以模拟运算，最后判断是否为1，不在赘述。
1.统计1的个数：二进制表示只有一个 1 存在为2的幂，否则不是。这里可以使用bitCount()和x & (x - 1)统计二进制中1的个数。
2.直接判断（推荐）：利用 1000 & 0111 == 0 这种性质可以直接得出是否为2的幂!
代码1：统计1的个数
public boolean isPowerOfTwo(int n) { if (n <= 0) { return false; } int cnt = 0; while (n > 0) { n &= (n - 1); cnt++; } return cnt == 1; } public boolean isPowerOfTwo(int n) { return n > 0 && Integer.bitCount(n) == 1; }
代码2：直接判断
public boolean isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; }
ps：运算符优先级口诀：单目乘除为（位）关系，逻辑三目后赋值。
7.4的幂（342-easy）
题目描述：给定一个整数n，编写一个函数来判断它是否是 4 的幂次方。
示例：
输入：n = 16 输出：true 输入：n = 1 输出：true
思路：这类问题基础操作还是循环，看最后的结果是否为1。不赘述。
1.统计奇数位1的个数：二进制表示中【有且只有一个奇数位为 1】，那么它是4的幂。
2.正则表达式：Integer.toString(int i, int radix):这个方法指的是将整数i（十进制）转化为radix进制的整数。
String.matches(): 这个方法主要是返回是否匹配指定的字符串，如果匹配则为true,否则为false; 同理，3的幂（326-easy）也可以用正则表达式匹配的方法。
3.数学推导：判断n = 4 ^ x,则x = log4 n = 1/2log2 n应该为整数，那么log2 n应该为偶数。使用换底公式！同理，3的幂（326-easy）也可以用数学推导的方法。
代码1：统计奇数位1的个数
public boolean isPowerOfFour(int n) { if (n <= 0 || (n & (n - 1)) != 0) return false; return (n & 0x55555555) == n; //也可替换 return n % 3 == 1; //return n > 0 && (n & (n - 1)) == 0 && (n & 0x55555555) == n; }
代码2：正则表达式匹配（效率比较低）
public boolean isPowerOfFour(int n) { return Integer.toString(n, 4).matches("10*"); //return Integer.toString(n, 3).matches("10*"); }
代码2：数学推导（换底公式）
public boolean isPowerOfFour(int n) { return n > 0 && (Math.log(n) / Math.log(2) % 2 == 0); // 不推荐 return n > 0 && (Math.log10(n) / Math.log10(3) % 1 == 0); //return n > 0 && 1162261467 % n == 0; }
ps:1162261467为整数范围内3的最大幂次（3^19）
8.比特位计数（338-medium）
题目描述：给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。要求：时间复杂度O(n)，空间复杂度O(n)，不使用内置函数。
示例：
输入: 2 输出: [0,1,1] 输入: 5 输出: [0,1,1,2,1,2]
思路：使用位运算+动态规划思想实现本题，都是利用数组前面已经算好的数来计算当前数的1的个数，原理相似，即维持i中1的个数。注:ret[i]]表示i这个数二进制表示中的1的个数！
1.方法1：使用i & (i - 1)将i二进制表示中最右边的1置0，所以i & (i - 1)一定小于i。本质利用ret[i & (i - 1)]已经计算过， 比如说我们要计算5（101）中1的个数，那么(5 & 4) = (100)中1的个数+1，即为结果。
2.方法2：使用i >>> 1将i二进制表示中最右边一位去掉，高位补0，所以i >>> 1一定小于i。本质利用ret[i >> 1]]已经计算过，比如说要计算6(110)中1的个数，那么(6 >> 1) = (011)，加上6 & 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; //ret[i] = ret[i >> 1] + (i & 1); } return ret; }
9.两整数之和（371-easy）
题目描述：不使用运算符 + 和 - ，计算两整数 a 、b 之和。
示例：
输入: a = 1, b = 2 输出: 3 输入: a = -2, b = 3 输出: 1
思路：本题不使用运算符和库函数，主要考察的还是如何模拟二进制运算（位运算模拟）。可递归和迭代，主要分为两步：
- 不考虑进位的两数和，通过两个整数按位异或（ps:异或结果为0时，需要判别是否为1 ^ 1 = 0，即进位）。
- 针对是否进位，可以通过两个整数按位与后左移一位（1 & 1 = 1， 即存在进位，需要将这一位左移）。
代码：
public int getSum(int a, int b) { // 左移为0说明不存在进位 // return b == 0 ? a : getSum(a ^ b, (a & b) << 1); while (b != 0) { int tmp = a ^ b; b = (a & b) << 1; a = tmp; } return a; }
10.交替二进制位（693-easy）
题目描述：给定一个正整数，检查它的二进制表示是否总是 0、1 交替出现：换句话说，就是二进制表示中相邻两位的数字永不相同。
示例：
输入：n = 5 输出：true 解释：5 的二进制表示是：101 输入：n = 11 输出：false 解释：11 的二进制表示是：1011.
思路：
- 常规解法：我们通过整除运算弹出最后1位，然后与剩下的数字的最后一位对比，相等就返回false，否则继续
- 位运算：可以将给定整数右移一位与原整数异或，异或后从右向左出现连续的1，+1检查连续性。例如10（1010），右移一位（101），与原数异或结果为（1010 ^ 0101 = 1111）；再如11（1011），右移一位（101），与原数异或结果（1011 ^ 0101 = 1110）。
代码：
public boolean hasAlternatingBits(int n) { // 注意是二进制 while (n > 0) { int pop = n % 2; n /= 2; if (n % 2 == pop) { return false; } } return true; } public boolean hasAlternatingBits(int n) { int num = n ^ (n >> 1); return (num & num + 1) == 0; }
11.数字的补码（476-easy）
题目描述：给定一个正整数，输出它的补数。补数是对该数的二进制表示取反。
示例：
输入: 5 输出: 2 解释: 5 的二进制表示为 101（没有前导零位），其补数为 010。所以你需要输出 2 。 输入: 1 输出: 0 解释: 1 的二进制表示为 1（没有前导零位），其补数为 0。所以你需要输出 0 。
思路：本题关键：如何获取二进制表示中指定数量的1， 利用异或运算（注：两个数相同为0，相异为1）进行0和1翻转。
- 循环获取，实现简单。例如（101 ^ 111 = 010）,（10 ^ 11 = 01）
- hashmap计算2的幂次思想：待补充。。。
代码：异或运算
public int findComplement(int num) { //注意num没有前导0位! int tmp = num, n = 0; while (tmp > 0) { tmp >>= 1; n = (n << 1) + 1; } return num ^ n; }
