位运算

一、位运算基础

1、& 按位与

如果两个相应的二进制位都为1，则该位的结果值为1，否则为0

2、| 按位或

两个相应的二进制位中只要有一个为1，该位的结果值为1

3、^ 按位异或

若参加运算的两个二进制位值相同则为0，否则为1

（1）异或运算的性质

    1.任意一个变量X与其自身进行异或运算，结果为0，即X ^ X=0
    2.任意一个变量X与0进行异或运算，结果不变，即X ^ 0=X
    3.异或运算具有可结合性，即a ^ b ^ c= (a ^ b) ^ c = a ^ (b ^ c)
    4.异或运算具有可交换性，即a ^ b = b ^ a

4、~ 取反

~是一元运算符，用来对一个二进制数按位取反，即0变1，1变0

5、<<N 左移

将一个数的各二进制位全部左移N位，右补0

6、>>N 右移

将一个数的各二进制位右移N位，移到右端的低位被舍弃，对于无符号数，高位补0

二、位运算的优点

1. 如果乘上一个2的次方的数，可以改用左移运算<< 快3倍

x = x * 2;
x = x * 128;
//改为:
x = x << 1; // 2 = 2^1
x = x << 7; // 128 = 2^7

2. 如果除上一个2的次方的数，可以改用右移运算>> 快 3.5倍

x = x / 2;
x = x / 128;
//改为:
x = x >> 1;// 2 = 2^1
x = x >> 7;// 64 = 2^7

3. 数值转整数加速 10%

x = int(1.232)
//改为:
x = 1.232 >> 0;

4. 交换两个数值(swap)，使用异或^ 可以加速20%

int a,b,t;
t = a;
a = b;
b = t;
//改为：
a = a^b;//
b = a^b;//实际为 a^b^b，而b^b为0，a^0为a，此时b记录的就是a的值
a = a^b;//实际为 a^b^a，而a^a为0，b^0为b，此时a记录的就是b的值

5. 用~实现正负号转换加快3倍

i = -i;
//改为
i =~i + 1; // ~写法，即取反在+1，即补码运算规则 //或
i = (i^-1)+1; // 异或 写法

6. 取余数，如果除数为 2 的次方的数，可利用 & 与运算快6倍

x = 131 % 4;
//equals:
原理：在移位运算中我们可知，计算机中的数据都是0和1的序列，当我们把某个数字左移一位，该数字会扩大为原来的2倍；而将其右移一位时，该数字就会缩小为原来的1/2，即相当于对该数字做了一次被2整除的运算。
11的二进制是1011，如果右移一位的话，将变成0101，也就是5。
现在我们考虑11除以8的余数，很显然是3；因为8是2的3次幂，求余时相当于除以2的3次幂，也就是把1011右移3位，该过程会把1011的低3位011给移走，事实上，这个被移走的011就是11除以8的余数！但是，我们该如何把这个011给保存下来呢？
现在的问题就转化为如何保存11的二进制1011的低三位数字了——这时就是按位与运算出马的时候了！和1做与运算会保存原来的数字，所以我们就可以用1011&0111来计算。那么这个0111又是如何得到的呢？
有两种方法，第一种是2^N-1，比如8按照此公式就得出了0111；第二种是8的二进制取反，即1000取反得到0111。
综上所述，位运算求余一定要注意，只适合于除数是2的N次方的情况。其原理就是：对2的N次方求余，就预示着数字将向右移N位；这被右移的N位，就是余数！只要我们再用与运算将这N位保存下来即可！
设X对Y求余，Y等于2^N，公式为：X & (2^N - 1)或X&(~Y)。 
x = 131 & (4 - 1);

7. 利用& 与运算检查整数是否为偶数，快6倍

if(x%2==0)
//equals:
if(x&1==0)

8. 加速 Math.abs 600% 的写法1，写法2 又比写法1加速 20%

//写法1
i = x < 0 ? -x : x;
//写法2
i = (x ^ (x >> 31)) - (x >> 31);
//写法3
i=x^(~(x>>31)+1)+(x>>31);

原理：正数和0的补码同原码，负数的补码是绝对值的反码加1。-1的补码表示是0xFFFFFFFF。
   任何一个非负整数（0~231-1）右移31位都是0；任何一个负整数（-231~-1）右移31位都是-1

9. 比较两数值相乘之后是否拥有相同的符号，加速 35%

c = a * b > 0;
//equals:
c = a ^ b > 0;

/*其它位运算技巧 //现在用不到，看一眼就行
1. RGB 色彩分离

var 24bitColor:uint = 0xff00cc;
var r:uint = 24bitColor >> 16;
var g:uint = 24bitColor >> 8 & 0xFF;
var b:uint = 24bitColor & 0xFF;

2. RGB 色彩合并

var r:uint = 0xff;
var g:uint = 0x00;
var b:uint = 0xcc;

var 24bitColor:uint = r << 16 | g << 8 | b;

三、位运算的一些使用技巧

1.用于消去x的二进制表示中的最后一位的1

x & (x-1)
x = 1100
x-1 = 1011
x & (x-1) = 1000

2.用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，即可判断。

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

思路：

由x&(x-1)消去最后一位1可知，循环使用直到为0，计算1的个数。这里x-1即为-x

代码模板：

#include<iostream>
using namespace std;
int lowbit(int n)
{
	return x&-x;			//返回的是最后一位一包括后面0的二进制数 
}
int main()
{
	int n;
	cin>>n;
	while(n--)
	{
		int x;
		cin>>x;
		int res=0;
		while(x)			//当x中还有1时 
		{
			x-=lowbit(x);	//减去最后一位1 
			res++;			//记录1的个数 
		}
		cout<<res<<" ";
	}
	return 0;
}