位运算是直接对整数在内存中的二进制位进行操作，而且不会对邻近位造成影响，不需要考虑进位的问题。

我们先来一道题热热身
leetcode 136. Single Number

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

这道题有很多解法，如何只用O(1)的额外空间？
我们来看一下异或^这个位运算:
1 ^ 1 = 0
1 ^ 0 = 1
0 ^ 0 = 0
0 ^ 1 = 1
可以推出： a ^ 0 = a, a ^ a = 0, 则 a ^ b ^ a = (a ^ a) ^ b = b
那么问题就很简单了，只要把所有的数按位异或，最后的结果就是只出现一次的那个数

1
2
3
4
5
6
7
8

public int singleNumber(int[] nums) {
    int a = 0;
    for(int i = 0; i < nums.length; i++){
        a ^= nums[i];
    }
    
    return a;
}

用位运算实现加法

lintcode 1 A+B问题

给出两个整数 a 和 b , 求他们的和。

看一下异或：
1 ^ 1 = 0
1 ^ 0 = 1
0 ^ 0 = 0
0 ^ 1 = 1
异或^可以看作不进位的加法，也就是说，a^b的结果是按位加法并且舍弃所有进位，我们把进位加上去就行了。
看一下&
1 & 1 = 1
1 & 0 = 0
0 & 0 = 0
0 & 1 = 0
是不是可以把结果看作是进位？但是还需要左移一位（相当于×2）再加之前的a ^ b就是结果了。
可以得出 a + b = ( a ^ b)+ ( a & b)
等式右边又出现了加号，我们只要用递归的思想就可以了,出口就是a&b为0,也就是没有进位了。

1
2
3
4
5

public int aplusb(int a, int b) {
    // write your code here
    if(b == 0) return b;
    return aplusb(a ^ b, (a &b) << 1);
}

判断奇偶

给出一个二进制：a=11111,当我们把它转成十进制时操作如下：

很明显，只有最后一位才会产生奇数，我们只要判断最后一位是1还是0就可以得出是奇数还是偶数。
&按位与可以用来取位，你想取a第n位，只要再构造一个二进制数,其第n位为1。这里我们要取得a的第1位数，构造一个 00001也就是1。
if(a^1 == 1)

交换两数

要求不使用第三个临时变量

1
2
3
4
5
6
7
8

void swap(int a, int b){
    if (a != b)
	{
		a ^= b;
		b ^= a;
		a ^= b;
	}
}

第一步：a ^=b =>：a = a^b
第二步：b ^=a => b ^(a^b) = b^b^a = a,b此时是a的值了
第三部：a ^=b => （a^b) ^ a = b,a此时是b的值了

位图法 bitmap

位图法是什么？百度百科-位图法

假设不允许数组的一项存储位图的一位，只能用32位整数，即一个整数代表32位bitmap，如果使用位逻辑运算来实现位向量？
C++代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N/BITSPERWORD];

//将指定位置为1
void set(int i ) {
    a[i>>SHIFT] |= (1<<(i & MASK));
}
//将指定位置为0
void clr(int i ){
    a[i>>SHIFT] &= ~(1<<(i & MASK));
}
int test(int i){
    return a[i>>SHIFT] & (1<<(i & MASK));
}

以下描述在二进制数第n位时都是指从右往左数：

• N表示bitmap一共需要多少位，1 + N/BITSPERWORD 就是一共需要多少个整数来存储这些bitmap。
• i>>SHIFT将i右移5位，也就是i/32,向下取整，得出第i位bitmap是在下标为几的整数上
• MASK是十六进制，转成二进制是 00011111，十进制是32
• i & MASK 取得了i（二进制）的后面5位的数字，也就是i / 32的余数
• 综上：将a[i>>SHIFT]写成二进制，第 (i & 32) 位就是在整个bitmap中的第i位

• 1<<(i & MASK) 左移i & MASK位 ，十进制即 $$2 ^(i \& 32)$$ 二进制是10000…0一共(i & 32)个零，第 1 + (i & 32)位是1。
• 按位与|：
  1 | 1 = 1
  1 | 0 = 0
  0 | 0 = 0
  0 | 1 = 1
  可以强制赋值为1，a|1不管a是几，结果都是1。
• set()函数中 a[i>>SHIFT] | (1<<(i & MASK)) 强行将a[i>>SHIFT]（二进制）第 1 + (i & MASK)位 设为1
• ~(1<<(i & MASK)) 按位取反变成11101111…1 只有从右往左第1 + (i \& 32)位为0,前面的
• clr()函数中 a[i>>SHIFT] & ~(1<<(i & MASK))取得a[i>>SHIFT] （二进制）除了第1 + (i & 32)位 的数，该数与a[i>>SHIFT]相比，唯一的不同就是第1 + (i & 32)位为0，其他位都一样。
• test()函数中 a[i>>SHIFT] & (1<<(i & MASK)),取得了a[i>>SHIFT]（二进制）第(i & 32) 位，前面已经得出，该位就是在整个bitmap中的第i位。

总结

• 按位与&：
  1. 取得两个数相加的进位
  2. 取位，取得某一位是1还是0
  3. 可以将指定位强行赋值为0，与取反~配合使用更佳
• 按位异或^：
  1. 看作不进位的加法
  2. a ^ 0 = a, a ^ a = 0： 任何数异或0等于自己，任何数异或自己等于0
  3. 有交换律
• 按位与|：
  可以将指定位强行赋值为1

参考链接

• 位操作基础篇之位操作全面总结
• 百度百科-位运算

• ← Previous Post
• Next Post →