2019 新春支付宝红包技术大揭秘在线峰会将于 03-07 日开始，点击这里报名届时即可参与大牛互动。
位运算表达式由操作数和位运算符组成，实现对整数类型的二进制数进行位运算。位运算符可以分为逻辑运算符 (包括~、&、| 和 ^) 及移位运算符(包括 >>、<< 和 >>>)。
1)左移位运算符（<<）能将运算符左边的运算对象向左移动运算符右侧指定的位数（在低位补 0）。
2)“有符号”右移位运算符（>>）则将运算符左边的运算对象向右移动运算符右侧指定的位数。“有符号”右移位运算符使用了“符号扩展”：若值为正，则在高位插入 0；若值为负，则在高位插入 1。
3)Java 也添加了一种“无符号”右移位运算符（>>>），它使用了“零扩展”：无论正负，都在高位插入 0。这一运算符是 C 或 C ++ 没有的。
4)若对 char，byte 或者 short 进行移位处理，那么在移位进行之前，它们会自动转换成一个 int。只有右侧的 5 个低位才会用到。这样可防止我们在一个 int 数里移动不切实际的位数。若对一个 long 值进行处理，最后得到的结果也是 long。此时只会用到右侧的 6 个低位，防止移动超过 long 值里现成的位数。但在进行“无符号”右移位时，也可能遇到一个问题。若对 byte 或 short 值进行右移位运算，得到的可能不是正确的结果（Java 1.0 和 Java 1.1 特别突出）。它们会自动转换成 int 类型，并进行右移位。但“零扩展”不会发生，所以在那些情况下会得到 - 1 的结果。
在进行位运算时，需要注意几点:
(1)>>> 和 >> 的区别是：在执行运算时，>>> 运算符的操作数高位补 0，而 >> 运算符的操作数高位移入原来高位的值。
(2)右移一位相当于除以 2，左移一位 (在不溢出的情况下) 相当于乘以 2；移位运算速度高于乘除运算。
(3)若进行位逻辑运算的两个操作数的数据长度不相同，则返回值应该是数据长度较长的数据类型。
(4)按位异或可以不使用临时变量完成两个值的交换，也可以使某个整型数的特定位的值翻转。
(5)按位与运算可以用来屏蔽特定的位，也可以用来取某个数型数中某些特定的位。
(6)按位或运算可以用来对某个整型数的特定位的值置 1。
位运算符的优先级
~ 的优先级最高，其次是 <<、>> 和 >>>，再次是&，然后是 ^，优先级最低的是 |。
位运算的应用
1. 判断 int 型变量 a 是奇数还是偶数
a&1 == 0 偶数
a&1 == 1 奇数
2. 求平均值，比如有两个 int 类型变量 x、y, 首先要求 x + y 的和，再除以 2，但是有可能 x + y 的结果会超过 int 的最大表示范围。
(x&y)+((x^y)>>1);
知识点：>>n 相当于除于 2^n，<<n 相当于乘于 2^n。
x,y 对应位均为 1，相加后再除以 2 还是原来的数，如两个 00001000 相加后除以 2 仍得 00001000, 那么我们把 x 与 y 分别分成两个部分来看, 两者相同的位分别拿出来 则 :
x = (111111111111000)2 = (111111111111000)2 + (000000000000000)2
y = (111111111111010)2 = (111111111111000)2 + (000000000000010)2
相同部分我们叫做 x1,y1, 不同部分我们叫做 x2,y2. 那么现在(x+y)/2 =(x1+y1)/2 +(x2 + y2)/2 , 因为 x1 == y1 , 所以(x1+y1)/2 ==x1 ==y1, 相同部分我们用与运算求出来 x1 = x&y , 不同部分的和我们用 ^ 求出来, 然后除于 2 就是我们想要的结果了。
3. 对于一个大于 0 的整数，判断它是不是 2 的几次方
((x&(x-1))==0)&&(x!=0)；
/* 如果是 2 的幂，n 一定是 100… n- 1 就是 1111….
所以做与运算结果为 0 */
4. 比如有两个 int 类型变量 x、y, 要求两者数字交换，位运算的实现方法
x ^= y;
y ^= x;
x ^= y;
5. 求绝对值
int abs(int x) {
int y ;
y = x >> 31 ;
return (x^y)-y ; //or: (x+y)^y
}
6. 取模运算，采用位运算实现
a % (2^n) 等价于 a & (2^n – 1) ; 或者 m % n 等价于 m & (n-1)
7. 乘法运算 采用位运算实现
a * (2^n) 等价于 a << n
8. 除法运算转化成位运算
a / (2^n) 等价于 a>> n
9. 求相反数
(~x+1)
10.a % 2 等价于
a & 1
11. 取 int 型变量 a 的第 k 位 (k=0,1,2……sizeof(int))
a>>k&1 (先右移再与 1)
12. 将 int 型变量 a 的第 k 位清 0
a&~(1<<k) (10000 取反后为 00001)
13. 将 int 型变量 a 的第 k 位置 1
a|(1<<k)
14.int 型变量循环左移 k 次
a<<k|a>>16-k (设 sizeof(int)=16)
15.int 型变量 a 循环右移 k 次
a>>k|a<<16-k (设 sizeof(int)=16)
16. 对于一个数 x >= 0，判断是不是 2 的幂。
boolean isPower2(int x) {
return ((x&(x-1))==0) && (x!=0);
}
17. 不用 temp 交换两个整数
void swap(int x , int y) {
x ^= y;
y ^= x;
x ^= y;
}
18. 条件判断赋值简写
if (x == a)
x= b;
else
x= a;
等价于 x= a ^ b ^ x;
19.x 的相反数
(~x+1)
20.m 乘以 2 的 n 次方
m << n
21.m 除以以 2 的 n 次方
m >> n
22. 求整数 k 从 x 位（高）到 y 位（低）间共有多少个 1
public static int findChessNum(int x, int y, int k) {
int result = 0;
for (int i = y; i <= x; i++) {
result += ((k >> (i – 1)) & 1);
}
return result;
}
23. 取绝对值
int abs(int n){
return (n ^ (n >> 31)) – (n >> 31);
}
/* n>>31 取得 n 的符号，若 n 为正数，n>>31 等于 0，若 n 为负数，n>>31 等于 -1
若 n 为正数 n^0=0, 数不变，若 n 为负数有 n^-1 需要计算 n 和 - 1 的补码，然后进行异或运算，结果 n 变号并且为 n 的绝对值减 1，再减去 - 1 就是绝对值 */
24. 只出现一次的数字给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。说明: 你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？示例 1:
输入: [2,2,1]输出: 1
示例 2:
输入: [4,1,2,1,2]输出: 4
这个题首先想到的就是异或的特性。相同的数字异或的结果为 0，那么出现奇数次的一定就是最后我们想要的结果。
public int singleNum(int[] nums){
int res = num[0];
for(int i=1;i<nums.length;i++){
res ^= nums[i];
}
return res;
}
总结
功能
示例
位运算
去掉最后一位
(101101->10110)
x >> 1
在最后加一个 0
(101101->1011010)
x < < 1
在最后加一个 1
(101101->1011011)
x < < 1+1
把最后一位变成 1
(101100->101101)
x | 1
把最后一位变成 0
(101101->101100)
x | 1-1
最后一位取反
(101101->101100)
x ^ 1
把右数第 k 位变成 1
(101001->101101,k=3)
x | (1 < < (k-1))
把右数第 k 位变成 0
(101101->101001,k=3)
x & ~ (1 < < (k-1))
右数第 k 位取反
(101001->101101,k=3)
x ^ (1 < < (k-1))
取末三位
(1101101->101)
x & 7
取末 k 位
(1101101->1101,k=5)
x & ((1 < < k)-1)
取右数第 k 位
(1101101->1,k=4)
x >> (k-1) & 1
把末 k 位变成 1
(101001->101111,k=4)
x | (1 < < k-1)
末 k 位取反
(101001->100110,k=4)
x ^ (1 < < k-1)
把右边连续的 1 变成 0
(100101111->100100000)
x & (x+1)
把右起第一个 0 变成 1
(100101111->100111111)
x | (x+1)
把右边连续的 0 变成 1
(11011000->11011111)
x | (x-1)
取右边连续的 1
(100101111->1111)
(x ^ (x+1)) >> 1
去掉右起第一个 1 的左边
(100101000->1000)
x & (x ^ (x-1))
判断奇数
(x&1)==1
判断偶数
(x&1)==0
点击阅读更多，查看更多详情