java 位操作

发表于

LeetCode 371.两整数之和

不使用运算符 + 和-，计算两整数a 、b之和。

题目考察的是基本的布尔代数知识。

二进制表示时：

0 + 0 = 00

1 + 0 = 01

0 + 1 = 01

1 + 1 = 10

所以一个二进制整数，在表示相加的过程中，如果没有进位的话其实尽是异或操作，如果单纯考虑进位的话其实是与操作然后和位操作。

采用递归写代码

1
2
3
4
5
6
7
8
9

public int getSum(int a, int b) {
       	if (b == 0){
          	 return a;
       	}
       	int sum = a ^ b;
       	int carry = (a & b)<<1;
       	return getSum(sum,carry);
   	}

整理一下位运算

符号 描述 运算规则
& 与 两个位都为1时，结果才为1
I 或 两个位都是 0 时，结果才为 0
^ 异或 两个位相同时为 0，相异为 1
~ 取反 0 变 1，1 变 0
<< 左移 各二进位全部左移若干位，高位丢弃，低位补 0
>> 右移 各二进位全部右移若干位，对无符号数，高位补 0，有符号数，各编译器处理方法不一样，有的补符号位(算术右移)，有的补 0 (逻辑右移)

注意以下几点:

  1. 在这6种操作符，只有 ~ 取反是单目操作符，其它5种都是双目操作符。
  2. 位操作只能用于整形数据，对 float 和 double 类型进行位操作会被编译器报错。
  3. 位操作符的运算优先级比较低，因为尽量使用括号来确保运算顺序，否则很可能会得到莫明其妙的结果。比如要得到像 1，3，5，9 这些 2^i+1 的数字。写成 int a = 1 << i + 1; 是不对的，程序会先执行 i + 1，再执行左移操作。应该写成 int a = (1 << i) + 1;
  4. 另外位操作还有一些复合操作符，如 &=、|=、 ^=、<<=、>>=

使用：

1. 判断奇偶性
2. 交换两数
3. 变换符号：变换符号只需要取反操作后加 1 即可
4. 求绝对值

    
1
2
int j = a >> 31;
System.out.println((a ^ j) - j);


5. 位操作与空间压缩

位操作技巧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
// 1. 获得int型最大值
System.out.println((1 << 31) - 1);// 2147483647， 由于优先级关系，括号不可省略
System.out.println(~(1 << 31));// 2147483647

// 2. 获得int型最小值
System.out.println(1 << 31);
System.out.println(1 << -1);

// 3. 获得long类型的最大值
System.out.println(((long)1 << 127) - 1);

// 4. 乘以2运算
System.out.println(10<<1);

// 5. 除以2运算(负奇数的运算不可用)
System.out.println(10>>1);

// 6. 乘以2的m次方
System.out.println(10<<2);

// 7. 除以2的m次方
System.out.println(16>>2);

// 8. 判断一个数的奇偶性
System.out.println((10 & 1) == 1);
System.out.println((9 & 1) == 1);

// 9. 不用临时变量交换两个数（面试常考）
a ^= b;
b ^= a;
a ^= b;

// 10. 取绝对值（某些机器上，效率比n>0 ? n:-n 高）
int n = -1;
System.out.println((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变号并且绝对值减1，再减去-1就是绝对值 */

// 11. 取两个数的最大值（某些机器上，效率比a>b ? a:b高）
System.out.println(b&((a-b)>>31) | a&(~(a-b)>>31));

// 12. 取两个数的最小值（某些机器上，效率比a>b ? b:a高）
System.out.println(a&((a-b)>>31) | b&(~(a-b)>>31));

// 13. 判断符号是否相同(true 表示 x和y有相同的符号， false表示x，y有相反的符号。)
System.out.println((a ^ b) > 0);

// 14. 计算2的n次方 n > 0
System.out.println(2<<(n-1));

// 15. 判断一个数n是不是2的幂
System.out.println((n & (n - 1)) == 0);
/*如果是2的幂，n一定是100... n-1就是1111....
所以做与运算结果为0*/

// 16. 求两个整数的平均值
System.out.println((a+b) >> 1);

// 17. 从低位到高位,取n的第m位
int m = 2;
System.out.println((n >> (m-1)) & 1);

// 18. 从低位到高位.将n的第m位置为1
System.out.println(n | (1<<(m-1)));
/*将1左移m-1位找到第m位，得到000...1...000
n在和这个数做或运算*/

// 19. 从低位到高位,将n的第m位置为0
System.out.println(n & ~(0<<(m-1)));
/* 将1左移m-1位找到第m位，取反后变成111...0...1111
n再和这个数做与运算*/
<<      :     左移运算符，num << 1,相当于num乘以2

>>      :     右移运算符，num >> 1,相当于num除以2

>>>     :     无符号右移，忽略符号位，空位都以0补齐