Java位运算总结
正数或负数在计算机中都以补码表示，位运算也是按照补码形式进行；正数最高位为0，负数最高位为1（无论是源码还是补码）；正数的补码与源码相同；负数的补码，符号位为1，其它位为其反码加1；
&：按位与。对于任意int型数字num，num & 0 = 0, num & 1=
，
|：按位或。对于任意int型数字num，num | 0 = num
num | 1将num二进制形式的最低位数置为1；
~：按位非。对于任意int型数字num，
^：按位异或。对于任意int型数字num，num ^ 0 = num
<<：左位移运算符。符号位不变，低位补0。对于任意int型数字num，无论正负，左移n位，相当于乘以
。
>>：右位移运算符。低位舍弃，高位用符号位填充。对于任意int型数字num，当num为正数时，右移n位，相当于除以
>>>：无符号右移运算符。低位舍弃，高位用0填充。
位运算使用技巧：
https://www.cnblogs.com/findbetterme/p/10787118.html
只出现一次的数字 (https://leetcode-cn.com/problems/single-number-iii/)
给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。
示例 :
输入: [1,2,1,3,2,5]
输出: [3,5]
注意：
结果输出的顺序并不重要，对于上面的例子， [5, 3] 也是正确答案。
你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？
位运算
首先了解一下一些基本异或运算的规律：
性质1：任何一个数和零进行异或运算，等于它自己；
性质2：2个相同的数进行异或运算结果为0；
性质3：x & (-x)：一个数和其相反数进行与操作，可以保留这个数（二进制形式）最右边的1。
结合本题的条件：
1）假设数组nums中只有一个元素出现一次，其他所有元素均出现两次，那么问题就简单了：所有数和0依次进行异或运算，结合上面的性质1和2，结果就是那个只出现一次的元素。
2）所以要想办法区分数组中只出现一次的两个元素：
所有数依次和0进行异或运算得到的结果： bitmask = single1 ^ single2；
利用性质3对bitmask进行运算：diff = bitmask & (-bitmask)；
diff中只有一位bit为1，其余bit全为0，且这个1要么属于single1，要么属于single2；利用这一点可以区分single1和single2；
3）得到single1和single2中的任意一个，通过与bitmask做异或运算，就得到另外一个；
public static int[] singleNumber(int[] nums) {
// bitmask = single1 ^ single2
int bitmask = 0;
for(int num : nums){
bitmask ^= num;
}
// 保留bitmask最右边的1, 其余为0; 这个值为1的bit要么属于x, 要么属于y
int diff = bitmask & (-bitmask);
int single1 = 0;
for(int num : nums){
if((num & diff) != 0){ // 只保留single1和single2的其中一个
single1 ^= num;
}
}
int single2 = bitmask ^ single1;
return new int[]{single1, single2};
}
只出现一次的数字 II
思路如下：
如下图所示，考虑数字的二进制形式，对于出现三次的数字，各 二进制位 出现的次数都是 33 的倍数。
因此，统计所有数字的各二进制位中 11 的出现次数，并对 33 求余，结果则为只出现一次的数字。
方法一：遍历统计
- int型数字num与1做&操作可获取对应的二进制数字的最右边一位
：
- 配合无符号右移操作，可依次获取num所有位的值（即
，
- 如何从num所有位的值（
在恢复后的num中也处于高位；
- 只需要修改求余数值 mm ，即可实现解决 除了一个数字以外，其余数字都出现 m次 的通用问题。
int ans = 0;
for(int i = 31; i >= 0; i--){
ans = ans << 1;
ans = ans | n[i];
}
完整代码如下：
public static int singleNumber2(int[] nums) {
int[] counts = new int[32];
for (int num : nums) {
for (int j = 0; j < 32; j++) { // 下标j，小数字代表低位，大数字代表高位，注意恢复时一致
counts[j] += num & 1;
num >>>= 1;
}
}
int res = 0, m = 3;
for (int i = 31; i >= 0; i--) {
res <<= 1;
res |= counts[i] % m;
}
return res;
}
方法二：有限状态自动机
解题的核心思路与方法一相同，但实现方式更加巧妙，但不容易想到，而且只针对于其它数字都出现3次的情况才适用，所以不做要求。
数组中两个数的最大异或值
字典树
- 确定可能的最大异或值
- 构建字典树
- 逐个遍历数字，得到最大的异或值：此步和上一步骤可以同时进行
1）遍历到3，得到的异或值为0，因为3是第一个数，还没有其它的数可以进行异或
2）遍历到10，得到的最大异或值为(01010)^(00011)，即10异或3。
3）遍历到5，得到的最大异或值为(00101)^(01010)，即5异或10，此时的值是5和(3,10)中可能的最大异或值。
4）遍历到25，得到的最大异或值为(11001)^(00101)，即25异或5，此时的值时25和(3,10,5)中可能的最大异或值
5）以此类推，当遍历完所有数时，即可得到最大的异或值。
下面给出第4）步的异或过程：其中绿色为当前数25走的路线(node)，蓝色为判断选择的最大异或值的对应路线(xorNode)。在每一层，如果找到相反的节点，则在当前异或值后添1；否则，添0；对应的实现就是
Character toggledBit = bit == '1' ? '0' : '1';
if (xorNode.children.containsKey(toggledBit)) {
currXor = (currXor << 1) | 1; // 在当前异或值后添1
xorNode = xorNode.children.get(toggledBit);
} else {
currXor = currXor << 1; // 在当前异或值后添0
xorNode = xorNode.children.get(bit);
}
class TrieNode {
HashMap<Character, TrieNode> children = new HashMap<Character, TrieNode>();
public TrieNode() {
}
}
public int findMaximumXOR(int[] nums) {
// Compute length L of max number in a binary representation
int maxNum = nums[0];
for (int num : nums) {
maxNum = Math.max(maxNum, num);
}
int L = (Integer.toBinaryString(maxNum)).length();
// zero left-padding to ensure L bits for each number
int n = nums.length;
int bitmask = 1 << L; // 1000...0: 低L位均为0
String[] strNums = new String[n];
for (int i = 0; i < n; ++i) {
strNums[i] = Integer.toBinaryString(bitmask | nums[i]).substring(1); // 补齐高位0, 而且刚好L位
}
TrieNode trie = new TrieNode(); // 跟节点
int maxXor = 0;
for (String num : strNums) {
TrieNode node = trie, xorNode = trie;
int currXor = 0;
for (Character bit : num.toCharArray()) {
// insert new number in trie
if (node.children.containsKey(bit)) {
node = node.children.get(bit);
} else {
TrieNode newNode = new TrieNode();
node.children.put(bit, newNode);
node = newNode;
}
// compute max xor of that new number
// with all previously inserted
Character toggledBit = bit == '1' ? '0' : '1';
if (xorNode.children.containsKey(toggledBit)) {
currXor = (currXor << 1) | 1; // 在当前异或值后添1
xorNode = xorNode.children.get(toggledBit);
} else {
currXor = currXor << 1; // 在当前异或值后添0
xorNode = xorNode.children.get(bit);
}
}
maxXor = Math.max(maxXor, currXor);
}
return maxXor;
}
利用哈希集合存储按位前缀
public int findMaximumXOR(int[] nums) {
int maxNum = nums[0];
for (int num : nums) {
maxNum = Math.max(maxNum, num);
}
// length of max number in a binary representation
int L = (Integer.toBinaryString(maxNum)).length();
int maxXor = 0, currXor;
Set<Integer> prefixes = new HashSet<>();
for (int i = L - 1; i > -1; --i) {
// go to the next bit by the left shift
maxXor <<= 1;
// set 1 in the smallest bit
currXor = maxXor | 1;
prefixes.clear();
// compute all possible prefixes
// of length (L - i) in binary representation
for (int num : nums) {
prefixes.add(num >> i);
}
for (int p : prefixes) {
if (prefixes.contains(currXor ^ p)) {
maxXor = currXor;
break;
}
}
}
return maxXor;
}
比特位计数
每个数字轮流解决
- 技巧点：x & x-1一个数和比自己小1的数做位与，相当将二进制形式的数的最低位1置为0；当重复这个操作，直至x为0后，重复的次数就是x中1的个数；
public int[] countBits(int num) {
int[] ans = new int[num + 1];
for (int i = 0; i <= num; ++i)
ans[i] = count(i);
return ans;
}
private int count(int x) {
int count;
for (count = 0; x != 0; ++count)
x &= x - 1; // 每次与x-1做按位与操作, 相当于将x中最低位的1置为0, 当所有1都置为0后, x值即0
return count;
}
动态规划
- 技巧点：i & 1用于判断i的奇偶性；1为奇，0为偶
public int[] countBits(int num) {
int[] ans = new int[num + 1];
for (int i = 1; i <= num; ++i)
ans[i] = ans[i >> 1] + (i & 1); // x / 2 is x >> 1 and x % 2 is x & 1
return ans;
}
