位运算的简单总结
在ACM训练中听老师讲了一些位运算的技巧，又看了大牛们写的关于位运算的一些总结，自己想学习学习，就把老师讲的和各位大牛们写的再总结一下，位运算通过位操作符的运算，可以简化一些复杂问题的计算。比如判断一个数是不是2的n次幂。是不是4的n次幂.
1.一些运算符的介绍与含义
运算符含义
&按位与
|按位或
^按位异或
~按位取反
【ACM_位运算|位运算的简单总结】<<左移
>>右移
2.位运算最简单的应用，判断一个数的奇偶性。
大家都知道判断一个数的奇偶性可以用n%2来判断，实际上奇数的二进制最后一位是1，偶数的二进制最后一位是0，因此只需要用n&1就可是判断这个数的奇偶性。结果为就是奇数，结果为0就是偶数。
3.用位运算来判断一个数是不是2的n次幂。
如果一个数是2的n次幂，则n&(n-1)==0；比如8的二进制是1000，则7的二进制就是0111，想与的到结果，这只是四位表示，在电脑中的32位或者64位表示的原理是一样，但如果这个数是0的话，n&(n-1)==0；所以判断一个数是不是2的正整数次幂的表达式是（！n&(n-1)&&n）
4 快速判断一个数是不是4的n次幂
我们刚才讲了快速判读一个数是不是2的n次幂，那么问题来了，能不能快速判断一个数是不是4的n次幂，4的二进制是0100，16的二进制是0001 0000，64的二进制是 0100 0000。我们可以发现4的n次幂二进制表达形式的权值都在奇数位上，即1出现在奇数位。那么16进制的A刚好是1010，奇数位都为0，那么n&0xAAAAAAAA（16进制表达，二进制一共32位）。如果结果为0，并且n！=0，那么n就是4的n次幂。判断式为n&(0xAAAAAAAA).
5.判断一个数组中只出现一次的数，而其他数都出现两次。
我们知道位运算的异或运算，两位相同的0，不同的1，那么两个相同的数进行异或运算，结果肯定为0，一个数与0进行异或运算，结果肯定是它本身。那么我们就可以的到判断的代码
int get_result(int a[n])
{
int result=0;
for(int i=0;
i6 判断一个数组中只出现一次的两个数，其它数都出现两次
刚才我们能判断只出现一次的一个数，那么我们同样进行异或运算，可以得到一个数c，假设两个只出现一次的数位a,b那么c=a^b.我们只需要找到c中二进制位权值为1的位，说明a和b在这两个位上的权值肯定不一样，一个是1，一个是0，那么我们可以根据这个位是1还是0，把数组中数分为两组分别进行异或运算，最终我们就得到了两个数。下面是我撸的代码
#include
using namespace std;
int a[100];
int main()
{
int n;
cin >> n;
int result=0;
int result1 = 0;
int result2 = 0;
for (int i = 0;
i < n;
i++)
{
cin >> a[i];
result ^= a[i];
//result最后的结果为a^b
}
int k = 1;
int count = 1;
//用来记录result中权值为1的为
while (result&k != 1)
{
count++;
k << 1;
//将1向左移动一位
}
for (int i = 0;
i < n;
i++)
{
if (a[i] & (1 << (k - 1)))//k-1为将1移到k位需要移动的位数，判断k为是1
{
result1 ^= a[i];
}
else
{
result2 ^= a[i];
} }
cout << result1 << ' ' << result2 << endl;
return 0;
} 判断数组中一个数出现一次，其它数都出现三次 同样用位运算的思想，但是不能直接用异或运算就能解决，首先我们知道一个数的二进制表达形式，不是1就是0，那么我们对二进制中的每个位相加mod3，最后的结果肯定是0，再把所有的数与0进行或运算，就可以得到我们要的数了。 测试代码：
#include
using namespace std;
int main()
{
int i,n;
int a[18];
int count[32]={0};
int result=0;
cin>>n;
for( i=0;
i>a[i];
}
for( i=0;
i<32;
i++)
{
for(int j=0;
j>i))//从低位依次向高位扫描，是1相加。将所有数二进制这个位上的和相加
{
count[i]++;
}
}
result|=((count[i]%3)< 7求二进制最低位的权值是多少，转化为10进制
n&(n-1)可以消去二进制最低位的1，如1100&1011得到1000，再用1100-1000就可以得到最低位的权值。n-(n&(n-1)).(没使用过这个公式，学习介绍一下)
8求一个数二进制中1的个数
while(n!=0){
count++;
n=n&(n-1);
}
也可以不断进行移位相与运算判断，没这种方法简单
8求商或者余数，更多用来取余运算
学了位运算，大家都知道2^k就是1<
说到取模运算，那我们不得不说神速的快速幂算法，首先得了解一下 秦九韶算法
把一个n次多项式f(x) = a[n]x^n+a[n-1]x^(n-1)+......+a[1]x+a[0]改写成如下形式：
f(x) = a[n]x^n+a[n-1]x^(n-1))+......+a[1]x+a[0]
= (a[n]x^(n-1)+a[n-1]x^(n-2)+......+a[1])x+a[0]
= ((a[n]x^(n-2)+a[n-1]x^(n-3)+......+a[2])x+a[1])x+a[0]
=. .....
= (......((a[n]x+a[n-1])x+a[n-2])x+......+a[1])x+a[0].
求多项式的值时，首先计算最内层括号内一次多项式的值，即
v[1]=a[n]x+a[n-1]
然后由内向外逐层计算一次多项式的值，即
v[2]=v[1]x+a[n-2]
v[3]=v[2]x+a[n-3]
......
v[n]=v[n-1]x+a[0]
这样，求n次多项式f(x)的值就转化为求n个一次多项式的值。
那么(a*b)%c=(a%c)*b%c
a^( 2^(i+1) ) mod c=( (a^(2^i)) mod c)^2 mod c
即a^(2^i)%c = ( (a^(2^(i-1))%c) * a^(2^(i-1))) %c
于是再把所有满足a(i)=1的a^(2^i)%c按照算法1乘起来再%c就是结果， 即二进制扫描从最高位一直扫描到最低位
任意一数都可以化为2的多少次幂相加。
ps:公式来自http://blog.sina.com.cn/s/blog_959bf1d301019hns.html
快速幂算法也需要这两个明显的公式
文章图片
我们就可以得到快速幂的迭代算法
int PowerMod(int a,int b,int c)
{
int ans=1;
a=a%c;
while(b>0)
{
if(a&1)//判断是奇数还是偶数
{
ans=ans*a%c;
}
b>>=1;
a=a*a%c;
}
return ans;
}
快速幂主要用来计算啊a^b%c=?b值非常非常大的时候
不用除法得到商和余数，计算机中的除法是通过减法来实现，我们可以模拟减法实现，如a/b可以写a-b-b……一直到的数小于b，为了加快速度，我们也可以a-b-2b-4b……,来实现
代码如下
#include
using namespace std;
int a[100];
int main()
{
int res=0;
//商
int mod=0;
//余数
int a;
//除数
int b;
//被除数
cin >> b>>a;
if (a < 0)
a = -a;
if (b < 0)
b = -b;
while (b >= a)
{
int temp = a;
int i = 0;
while (b >=temp )
{
b -= temp;
res += 1 << i;
i++;
temp <<= 1;
}
}
mod = b;
if ((a > 0 && b < 0) || (a < 0 && b>0))
{
res = -res;
}
cout << res << ' ' << mod << endl;
return 0;
} 9：整数的平均值
对于两个整数x,y，如果用 (x+y)/2 求平均值，会产生溢出，因为 x+y 可能会大于INT_MAX，但是我们知道它们的平均值是肯定不会溢出的，我们用如下算法：
int average(int x, int y) //返回X,Y 的平均值
{
return (x&y)+((x^y)>>1);
}10.位运算的其它一些技巧
功能 | 示例 | 位运算
----------------------+---------------------------+--------------------
去 掉最后一位 | (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))
先总结这么多吧，以后遇到再加上………………
