Bit Manipulation

各种位运算的使用

and运算

​ and运算通常用于二进制取位操作,例如一个数 and 1的结果就是取二进制的最末位。这可以用来判断一个整数的奇偶,二进制的最末位为0表示该数为偶数,最末位为1表示该数为奇数.

or运算

​ or运算通常用于二进制特定位上的无条件赋值,例如一个数or 1的结果就是把二进制最末位强行变成1。如果需要把二进制最末位变成0,对这个数or 1之后再减一就可以了,其实际意义就是把这个数强行变成最接近的偶数。

xor运算

xor运算通常用于对二进制的特定一位进行取反操作,因为异或可以这样定义:0和1异或0都不变,异或1则取反。

xor运算的逆运算是它本身,也就是说两次异或同一个数最后结果不变,即(a xor b) xor b = a。xor运算可以用于简单的加密。

定义两个符号#和@ ,这两个符号互为逆运算,也就是说(x # y) @ y = x。现在依次执行下面三条命令,结果是什么?
x <- x # y

y <- x @ y

x <- x @ y
执行了第一句后x变成了x # y。那么第二句实质就是y <- x # y @ y,由于#和@互为逆运算,那么此时的y变成了原来的x。第三句中x实际上被赋值为(x # y) @ x,如果#运算具有交换律,那么赋值后x就变成最初的y了。

这三句话的结果是,x和y的位置互换了。
加法和减法互为逆运算,并且加法满足交换律。把#换成+,把@换成-,我们可以写出一个不需要临时变量的swap过程。

1
2
3
4
5
6
procedure swap(var a,b:longint);
begin
a:=a + b;
b:=a - b;
a:=a - b;
end;

好了,刚才不是说xor的逆运算是它本身吗?于是我们就有了一个看起来非常诡异的swap过程:

1
2
3
4
5
6
procedure swap(var a,b:longint);
begin
a:=a xor b;
b:=a xor b;
a:=a xor b;
end;

not运算

not运算的定义是把内存中的0和1全部取反。使用not运算时要格外小心,你需要注意整数类型有没有符号。如果not的对象是无符号整数(不能表示负数),那么得到的值就是它与该类型上界的差,因为无符号类型的数是用$0000到$FFFF依次表示的。下面的两个程序(仅语言不同)均返回65435。

1
2
3
4
5
6
7
var
a:word;
begin
a:=100;
a:=not a;
writeln(a);
end.
1
2
3
4
5
6
7
8
#include <stdio.h>
int main()
{
unsigned short a=100;
a = ~a;
printf( "%dn", a );
return 0;
}

如果not的对象是有符号的整数,情况就不一样了,稍后我们会在“整数类型的储存”小节中提到。

shl运算

a shl b就表示把a转为二进制后左移b位(在后面添b个0)。例如100的二进制为1100100,而110010000转成十进制是400,那么100 shl 2 = 400。可以看出,a shl b的值实际上就是a乘以2的b次方,因为在二进制数后添一个0就相当于该数乘以2。
​ 通常认为a shl 1比a * 2更快,因为前者是更底层一些的操作。因此程序中乘以2的操作请尽量用左移一位来代替。
​ 定义一些常量可能会用到shl运算。你可以方便地用1 shl 16 – 1来表示65535。很多算法和数据结构要求数据规模必须是2的幂,此时可以用shl来定义Max_N等常量。

shr运算

和shl相似,a shr b表示二进制右移b位(去掉末b位),相当于a除以2的b次方(取整)。我们也经常用shr 1来代替div 2,比如二分查找、堆的插入操作等等。想办法用shr代替除法运算可以使程序效率大大提高。最大公约数的二进制算法用除以2操作来代替慢得出奇的mod运算,效率可以提高60%。


技巧

用于消去x的最后一位的1

1
2
3
4
x & (x-1)
x = 1100
x-1 = 1011
x & (x-1) = 1000

用O(1)时间检测整数n是否是2的幂次.

思路解析:N如果是2的幂次,则N满足两个条件。
1.N>0
2.N的二进制表示中只有一个1
一位N的二进制表示中只有一个1,所以使用N&(N-1)将唯一的一个1消去。
如果N是2的幂次,那么N&(N-1)得到结果为0,即可判断。

计算在一个 32 位的整数的二进制表示中有多少个 1.

由 x & (x-1) 消去x最后一位知。循环使用x & (x-1)消去最后一位1,计算总共消去了多少次即可。

将整数A转换为B,需要改变多少个bit位

思考将整数A转换为B,如果A和B在第i(0<=i<32)个位上相等,则不需要改变这个BIT位,如果在第i位上不相等,则需要改变这个BIT位。所以问题转化为了A和B有多少个BIT位不相同。联想到位运算有一个异或操作,相同为0,相异为1,所以问题转变成了计算A异或B之后这个数中1的个数。

使用二进制进行子集枚举

给定一个含不同整数的集合,返回其所有的子集

样例 如果 S = [1,2,3],有如下的解: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2] ]
思路就是使用一个正整数二进制表示的第i位是1还是0,代表集合的第i个数取或者不取。所以从0到2n-1总共2n个整数,正好对应集合的2^n个子集。

1
2
3
4
5
6
7
8
9
10
S = {1,2,3}
N bit Combination
0 000 {}
1 001 {1}
2 010 {2}
3 011 {1,2}
4 100 {3}
5 101 {1,3}
6 110 {2,3}
7 111 {1,2,3}

a^b^b=a

数组中,只有一个数出现一次,剩下都出现两次,找出出现一次的。

问题 Given [1,2,2,1,3,4,3], return 4

因为只有一个数恰好出现一个,剩下的都出现过两次,所以只要将所有的数异或起来,就可以得到唯一的那个数。

1
2
3
4
5
6
7
8
9
10
#include<stdio.h>
int main()
{
int a[7]={1,2,2,1,3,4,3};
int ans=0;
for(int i=0;i<7;i++){
ans^=a[i];
}
printf("%d\n",ans);
}

数组中,只有一个数出现一次,剩下都出现三次,找出出现一次的。

问题 Given [1,1,2,3,3,3,2,2,4,1] , return 4

因为数是出现三次的,也就是说,对于每一个二进制位,如果只出现一次的数在该二进制位为1,那么这个二进制位在全部数字中出现次数无法被3整除。
模3运算只有三种状态:00,01,10,因此我们可以使用两个位来表示当前位%3,对于每一位,我们让Two,One表示当前位的状态,B表示输入数字的对应位,Two+和One+表示输出状态。

0 0 0 0 0
0 0 1 0 1
0 1 0 0 1
0 1 1 1 0
1 0 0 1 0
1 0 1 0 0
One+ = (One ^ B) & (~Two)
Two+ = (~One+) & (Two ^ B)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<stdio.h>

void findNum(int *a,int n)
{
int one=0;
int two=0;
int i,j,k;
for(i=0;i<n;i++){
two=two|(one&a[i]);
one=one^a[i];
int three=two&one;
two=two^three;
one=one^three;
}
printf("%d\n",one|two);
}
int main()
{
int a[10]={1,1,2,3,3,3,2,2,4,1};
findNum(a,10);
}

另外一种容易理解的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<stdio.h>

void findNum(int *a,int n)
{
int ans=0;
int bits[32]={0};
for(int i=0;i<n;i++){
for(int j=0;j<32;j++){
bits[j]+=((a[i]>>j)&1);
}
}
for(int i=0;i<32;i++){
if(bits[i]%3==1) ans+=1<<i;
}
printf("%d\n",ans);
}
int main()
{
int a[10]={1,1,2,3,3,3,2,2,4,1};
findNum(a,10);
}

数组中,只有两个数出现一次,剩下都出现两次,找出出现一次的

问题 Given [1,2,2,3,4,4,5,3] return 1 and 5
有了第一题的基本的思路,我们不妨假设出现一个的两个元素是x,y,那么最终所有的元素异或的结果就是res = x^y。并且res!=0,那么我们可以找出res二进制表示中的某一位是1,那么这一位1对于这两个数x,y只有一个数的该位置是1。对于原来的数组,我们可以根据这个位置是不是1就可以将数组分成两个部分。求出x,y其中一个,我们就能求出两个了。

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
#include<stdio.h>

void findNum(int *a,int n)
{
int ans=0;
int pos=0;
int x=0,y=0;
for(int i=0;i<n;i++)
ans^=a[i];
int tmp=ans;
while((tmp&1)==0){
//终止条件是二进制tmp最低位是1
pos++;
tmp>>=1;
}
for(int i=0;i<n;i++){
if((a[i]>>pos)&1){//取出第pos位的值
x^=a[i];
}
}
y=x^ans;
if(x>y) swap(x,y);//从大到小输出x,y
printf("%d %d\n",x,y);
}
int main()
{
int a[8]={1,2,2,3,4,4,5,3};
findNum(a,8);
}

另外一种写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<stdio.h>

void findNum(int *a,int n)
{
int diff=0;
int x=0,y=0;
for(int i=0;i<n;i++){
diff^=a[i];
}
diff&=-diff;//取diff的最后一位1的位置
for(int i=0;i<n;i++){
if((a[i]&diff)==0){
x^=a[i];
}else y^=a[i];
}
if(x>y) swap(x,y);
printf("%d %d\n",x,y);
}
int main()
{
int a[10]={1,2,2,3,4,4,5,3};
findNum(a,8);
}
Thanks for Support.