位运算学习总结

位运算算法题非算法题

位运算

位运算不仅仅是二进制数字的移动，还包括逻辑运算。常见逻辑运算就是与运算、或运算、异或运算、同或运算等等。首先最基础的就是数字的移动： 比如数字5，二进制数字是101(2)，分别左移和右移一位结果：

1 int data = 5; 2 int rightShift = data>>1; //右移一位 3 int leftShift = data<<1; //左移一位 4 System.out.println("右移结果:" + rightShift); 5 System.out.println("左移结果:" + leftShift);

运行结果：右移后二进制变为10(2) , 左移一位后就是1010(2)。 逻辑运算，与运算即有0就为0，或运算就是有1就是1,，以5(101)和12(1100)为例：

1 int data1 = 5; 2 int data2 = 12; 3 int andData = data1 & data2; 4 int orData = data1 | data2; 5 System.out.println("与运算结果:" + andData); 6 System.out.println("或运算结果:" + orData);

应用：移位运算是高效的运算，可以代替乘除，一个数字每左移一位即数字乘以2，每右移一位即数字除以2，那么举例：

2乘以8，2左移三位即可，相当于2乘以8 : 2<<3. 8除以8，8右移三位即可，相当于8除以8 : 8>>3

异或运算：这是算法题中常见的。异或就是相同为false，不同为true，0与任何数异或都是那个数本身，自己和自己异或结果是0。与之对应的就是同或运算，相同为true，不同为false。

1 int data1 = 5; 2 int data2 = 12; 3 int XORData = data1 ^ data2; 4 System.out.println("异或运算结果:" + XORData);

非运算，是对自己的运算，每个位取反即可，0位变为1,1位变为0.

算法题

LeetCode上有很多典型的关于位运算的题目。最基础的一道也是出现频率高的就是找出数组中唯一出现一次的数。

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

根据异或性质，两个相同数异或结果是0，所以将数组所有数异或，结果就是唯一出现一次的数。

1 class Solution { 2 public int singleNumber(int[] nums) { 3 int len = nums.length; 4 int res = 0; 5 for (int i = 0 ; i < len ; i ++) { 6 res ^= nums[i]; 7 } 8 return res; 9 } 10 }

137. 只出现一次的数字 II：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现一次元素。 遍历每个位，数组所有数相加后，当前位的值要么是3的倍数，要么是0或者1，所以每个位遍历一遍后算出每个位置，再结合每个位结果。

1 class Solution { 2 public int singleNumber(int[] nums) { 3 int res = 0; 4 for (int i = 0 ; i < 32 ; i ++) { 5 int sum = 0; 6 for (int num : nums) 7 sum += (num>>i) & 1; 8 res ^= (sum%3 <<i); 9 } 10 return res; 11 } 12}

260. 只出现一次的数字 III：给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。 所有数异或后结果就是那两个数异或的结果，结果位值是1就表示这两个数当前位不一样，所以可以随机选一个位值是1的位，进行分组，将两个元素分在两个组内，两个组内所有结果异或，那么异或值就是只出现一次的那个。

1 class Solution { 2 public int[] singleNumber(int[] nums) { 3 int len = nums.length; 4 int XORData = 0; 5 for (int num : nums) 6 XORData ^= num; 7 int index = 1; 8 //找最右边为位值为1的那个位 9 while ((XORData & index) == 0) { 10 index = index<<1; 11 } 12 //分组异或 13 int res1 = 0; int res2 = 0; 14 for (int num : nums) { 15 if ((num & index) == index) res1 ^= num; 16 if ((num & index) != index) res2 ^= num; 17 } 18 return new int[]{res1 , res2}; 19 } 20}

421 数组中两个数的最大异或值：

给定一个非空数组，数组中元素为 a0, a1, a2, … , an-1，其中 0 ≤ ai < 231 。找到 ai 和aj 最大的异或 (XOR) 运算结果，其中0 ≤ i, j < n 。你能在O(n)的时间解决这个问题吗？

最大的异或 最大就是最大数的二进制表示的最大数，比如25 = 11001(2)，最大只可能是11111(2)，不能再大了。那么就按照最大二进制数按位遍历。就是这个位可不可能是1。

1 class Solution { 2 public int findMaximumXOR(int[] nums) { 3 int len = nums.length; 4 int maxData = nums[0]; 5 for (int num : nums) maxData = Math.max(maxData , num); 6 int stringLen = Integer.toBinaryString(maxData).length(); 7 8 HashSet<Integer> set = new HashSet<>(16); 9 int maxXor = 0 , curXor = 0; 10 //遍历最长二进制数字 11 for (int i = stringLen - 1 ; i >= 0 ; i--) { 12 //让位一个下一个最大值 13 maxXor <<= 1; 14 //假设当前是最大的，最右一位掷1，就是看数组中前stringLen-i位是否有两个值异或等于curXor 15 curXor = maxXor | 1; 16 set.clear(); 17 for (int num : nums) set.add(num>>i); 18 //是否存在p1^p2 == curXor ,也就是 p1 = curXor^p2是否存在 19 for (int num : nums) { 20 if (set.contains((num>>i)^curXor)) { 21 maxXor = curXor; 22 break; 23 } 24 } 25 } 26 return maxXor; 27 } 28 }

268 缺失数字：给定一个包含 0, 1, 2, …, n 中 n 个数的序列，找出 0 … n 中没有出现在序列中的那个数。

[0 , n]所有数据加上数组中所有数据异或，那么结果就是只出现一次的值，也就是[0 , n]中没有出现在序列中的数。

1 class Solution { 2 public int missingNumber(int[] nums) { 3 int len = nums.length; 4 for (int i = 0 ; i < nums.length ; i++) { 5 len ^= (i^nums[i]); 6 } 7 return len; 8 } 9 }

非算法题

正是因为位运算的高效性，在一些技术大佬写的代码或者源码中都能看见位运算，这些小细节也体现了编程者的技术功底和细节严谨。很值得自己学习。

求2的余数：n & 1 求2的幂次方的余数: n%a = n & b - 1

HashTable源码中的位运算：

空间初始化：

1 //默认的初始化容量为16，必须是2的n次幂 2 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 3 //最大容量为 2^30 4 static final int MAXIMUM_CAPACITY = 1 << 30;

tableSizeFor()函数： 将传入的初始化大小值转化为大于这个数的最小的2的幂方数

1 static final int tableSizeFor(int cap) { 2 int n = cap - 1; 3 n |= n >>> 1; 4 n |= n >>> 2; 5 n |= n >>> 4; 6 n |= n >>> 8; 7 n |= n >>> 16; 8 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; 9 }

hash()计算原理：哈希值h和右移16位后作异或运算，尽量保持高16位特征，减少哈希碰撞。异或是因为让0和1分布均匀，从而哈希值分布均匀，也是为了减少哈希碰撞。

1 static final int hash(Object key) { 2 int h; 3 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16 ); 4 }

put()函数取模：与运算取模

1 //这是 put 方法中用来根据hash()值寻找在数组中的下标的逻辑， 2 //n为数组长度， hash为调用 hash()方法混合处理之后的hash值。 3 i = (n - 1) & hash

& 和 && 的区别:

&运算两种用法: （1）按位与；(2)逻辑与 &&运算符是短路与运算。两者都是要求运算符左右两端的布尔值都是true整个表达式才是true，但两者是有区别的。&&被称为短路运算是因为如果&&左边表达式值是false。右边表达式会直接被短路，不会进行运算。 逻辑或运算(|) 和短路或运算符(||)差别也是如此。