⭐️位运算⭐️
🌍1. 位运算的介绍
因为计算机内部的运算都是基于二进制的，所以位运算一般都比其他运算快。
🌍2. 位运算基础
Java 中的 算术右移 和 逻辑右移 。
算术右移 >> ：舍弃最低位，高位用符号位填补；
逻辑右移 >>> ：舍弃最低位，高位用 0 填补。
那么对于负数而言，其二进制最高位是 1，如果使用算术右移，那么高位填补的仍然是 1。也就是 n 永远不会为 0。
🌍3. 位运算操作
🍀3.1判断奇偶数
一般我们去判断一个数是基数还是偶数时会采用以下算法：
if( n % 2 != 1)
// n 是个奇数
}
如果把 n 以二进制的形式展示的话，其实我们只需要判断最后一个二进制位是 1 还是 0 就行了，如果是 1 的话，代表是奇数，如果是 0 则代表是偶数，所以采用位运算的方式的话，代码如下：
if(n & 1 == 1){
// n 是个奇数。
}
🍀3.2LowBit(二进制数中最后一个1)
x&(-x)，得x的二进制数中最后一个1与后面的0组成的十进制数。
📚举例分析：
比如：x=20,其二进制为10100
则x&(-x)为求二进制数100的十进制数
所以x&(-x)=4
public class LowBit {
public static void main(String[] args) {
int x=20;
System.out.println(x&(-x));//4
}
}
🍀3.3 消去x的最后一位的1
x & (x-1)
x = 1100
x-1 = 1011
x & (x-1) = 1000
3.3.1应用一 用O(1)时间检测整数n是否是2的幂次
if (X&(X-1)==O)
📒思路解析：
N如果是2的幂次，则N满足两个条件。
1.N>0
2.N的二进制表示中只有一个1
一位N的二进制表示中只有一个1，所以使用N&(N-1)将唯一的一个1消去。
如果N是2的幂次，那么N&(N-1)得到结果为0，即可判断。
3.3.2应用二 计算在一个二进制表达式中数字位数为 ‘1’ 的个数
题目：191. 位1的个数
📒思路解析：
由 x & (x-1) 消去x最后一位知。循环使用x & (x-1)消去最后一位1，计算总共消去了多少次即可。
🍀3.4交换两个数
假如有x，y两个数，一次进行下面三个操作即可交换这两个数的值:
public class 交换两个数 {
public static void main(String[] args) {
int x=1;
int y=2;
x = x ^ y;//一
y = x ^ y;//二
x = x ^ y;//三
System.out.println("x="+x);
System.out.println("y="+y);
}
}
📒思路解析：
两个相同的数异或之后结果会等于 0，即 n ^ n = 0。并且任何数与 0 异或等于它本身，即 n ^ 0 = n。
把（1）中的 x 带入(2)中的x,有
y = x ^ y = (x ^ y) ^ y = x^ (y ^ y) = x^0 = x。 x 的值成功赋给了 y。
对于(3）,推导如下：
x = x^y = (x^y)^x = (x^x)^y = 0^y = y。
🍀3.5找出没有重复的数
给你一组整型数据，这些数据中，其中有一个数只出现了一次，其他的数都出现了两次，让你来找出一个数 。
📒思路解析：
前面已经说过：任何数异或上0都等于他本身，任何数异或上两次都为0。 例如这组数组a={1,2,3,4,5,1,2,3,4}。其中 5 只出现了一次，其他都出现了两次，把他们全部异或一下，结果如下：
1^2^3^4^5^1^2^3^4 = （1^1)^(2^2)^(3^3)^(4^4)^5= 0^0^0^0^5 = 5(异或支持交换律和结合律)
其中出现了两次的数异或之后会变成0，那个出现一次的数，和 0 异或之后就等于它本身。
代码：
int find(int[] arr){
int tmp = arr[0];
for(int i = 1;i < arr.length; i++){
tmp = tmp ^ arr[i];
}
return tmp;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/199756.html
