位运算
位运算基础
&
按位与
如果两个相应的二进制位都为1，则该位的结果值为1，否则为0
|
按位或
两个相应的二进制位中只要有一个为1，该位的结果值为1
^
按位异或
若参加运算的两个二进制位值相同则为0，否则为1
~
取反
~是一元运算符，用来对一个二进制数按位取反，即将0变1，将1
<<
左移
用来将一个数的各二进制位全部左移N位，右补0
>>
右移
将一个数的各二进制位右移N位，移到右端的低位被舍弃，对于无符号数， 高位补0
奇技淫巧
1.技巧一：用于消去x的最后一位的1
x & (x-1)
x = 1100
x-1 = 1011
x & (x-1) = 1000
1.1.应用一 用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，即可判断。
1.2.应用二 计算在一个 32 位的整数的二进制表示中有多少个 1.
思路解析：
由 x & (x-1) 消去x最后一位知。循环使用x & (x-1)消去最后一位1，计算总共消去了多少次即可。
1.3.将整数A转换为B，需要改变多少个bit位
思路解析
这个应用是上面一个应用的拓展。
思考将整数A转换为B，如果A和B在第i（0<=i<32）个位上相等，则不需要改变这个BIT位，如果在第i位上不相等，则需要改变这个BIT位。所以问题转化为了A和B有多少个BIT位不相同。联想到位运算有一个异或操作，相同为0，相异为1，所以问题转变成了计算A异或B之后这个数中1的个数。
2.技巧二 使用二进制进行子集枚举
应用.给定一个含不同整数的集合，返回其所有的子集
样例
如果 S = [1,2,3]，有如下的解：
[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2] ]
思路
思路就是使用一个正整数二进制表示的第i位是1还是0，代表集合的第i个数取或者不取。所以从0到2^n-1总共2^n个整数，正好对应集合的2^n个子集。
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
3.1.应用一 数组中，只有一个数出现一次，剩下都出现三次，找出出现一次的。
问题
Given [1,2,2,1,3,4,3], return 4
解题思路
因为只有一个数恰好出现一个，剩下的都出现过两次，所以只要将所有的数异或起来，就可以得到唯一的那个数。
C语言解题代码
#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);
}
3.2.应用二 数组中，只有一个数出现一次，剩下都出现三次，找出出现一次的。
问题
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)
C语言解题代码
#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);
}
另外一种容易理解的方法
#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);
}
3.3.应用三 数组中，只有两个数出现一次，剩下都出现两次，找出出现一次的
问题
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其中一个，我们就能求出两个了。C语言解题代码
#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);
}另外一种写法
#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);
}