位运算技巧总结.docx

位运算应用口诀
清零取反要用与，某位置一可用或
(1&0=0,1|1=1、0｜1=1)
若要取反和交换，轻轻松松用异或
(与1异或相当于取反，与0异或相当于不变。1^1=0、0^1=1，1^0=1、0^0=0)
移位运算要点
1 它们都是双目运算符，两个运算分量都是整形，结果也是整形。
2 " < <" 左移：右边空出的位上补0，左边的位将从字头挤掉，其值相当于乘2。
3 ">>"右移：右边的位被挤掉。对于左边移出的空位，如果是正数则空位补0，若为负数，可能补0或补1，这取决于所用的计算机系统。
4 ">>>"运算符，右边的位被挤掉，对于左边移出的空位一概补上0。
位运算符的应用 (源操作数s 掩码mask)
(1) 按位与-- &
1 清零特定位 (mask中特定位置0，其它位为1，s=s&mask)
2 取某数中指定位 (mask中特定位置1，其它位为0，s=s&mask)
(2) 按位或-- |
常用来将源操作数某些位置1，其它位不变。 (mask中特定位置1，其它位为0 s=s |mask)
(3) 位异或-- ^
1 使特定位的值取反 (mask中特定位置1，其它位为0 s=s^mask)
2 不引入第三变量，交换两个变量的值 (设 a=a1,b=b1)
目 标 操 作 操作后状态
a=a1^b1 a=a^b a=a1^b1,b=b1
b=a1^b1^b1 b=a^b a=a1^b1,b=a1
a=b1^a1^a1 a=a^b a=b1,b=a1
二进制补码运算公式：
-x = ~x + 1 = ~(x-1)
~x = -x-1
-(~x) = x+1
~(-x) = x-1
x+y = x - ~y - 1 = (x |y)+(x&y)
x-y = x + ~y + 1 = (x |~y)-(~x&y)
x^y = (x |y)-(x&y)
x |y = (x&~y)+y
x&y = (~x |y)-~x
x==y: ~(x-y |y-x)
x!=y: x-y |y-x
x < y: (x-y)^((x^y)&((x-y)^x))
x <=y: (x |~y)&((x^y) |~(y-x))
x < y: (~x&y) |((~x |y)&(x-y))//无符号x,y比较
x <=y: (~x |y)&((x^y) |~(y-x))//无符号x,y比较
应用举例
(1) 判断int型变量a是奇数还是偶数
a&1 = 0 偶数
a&1 = 1 奇数
(2) 取int型变量a的第k位 (k=0,1,2……sizeof(int))，即a>>k&1
(3) 将int型变量a的第k位清0，即a=a&~(1 < <k)
(4) 将int型变量a的第k位置1， 即a=a |(1 < <k)
(5) int型变量循环左移k次，即a=a < <k |a>>16-k (设sizeof(int)=16)
(6) int型变量a循环右移k次，即a=a>>k |a < <16-k (设sizeof(int)=16)
(7)整数的平均值
对于两个整数x,y，如果用 (x+y)/2 求平均值，会产生溢出，因为 x+y 可能会大于INT_MAX，但是我们知道它们的平均值是肯定不会溢出的，我们用如下算法：
int average(int x, int y) //返回X,Y 的平均值
{
return (x&y)+((x^y)>>1);
}
(8)判断一个整数是不是2的幂,对于一个数 x >= 0，判断他是不是2的幂
boolean power2(int x)
{
return ((x&(x-1))==0)&&(x!=0)；
}
(9)不用temp交换两个整数
void swap(int x , int y)
{
x ^= y;
y ^= x;
x ^= y;
}
(10)计算绝对值
int abs( int x )
{
int y ;
y = x >> 31 ;
return (x^y)-y ; //or: (x+y)^y
}
(11)取模运算转化成位运算 (在不产生溢出的情况下)
a % (2^n) 等价于 a & (2^n - 1)
(12)乘法运算转化成位运算 (在不产生溢出的情况下)
a * (2^n) 等价于 a < < n
(13)除法运算转化成位运算 (在不产生溢出的情况下)
a / (2^n) 等价于 a>> n
例: 12/8 == 12>>3
(14) a % 2 等价于 a & 1
(15) if (x == a) x= b;
　　 else x= a;
　　 等价于 x= a ^ b ^ x;
(16) x 的 相反数 表示为 (~x+1)

实例

功能 | 示例 | 位运算
----------------------+---------------------------+--------------------
去掉最后一位 | (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))
判断奇数 (x&1)==1
判断偶数 (x&1)==0

例如求从x位（高）到y位（低）间共有多少个1

public static int FindChessNum(int x, int y, ushort k)
{
int re = 0;
for (int i = y; i <= x; i++)
{
re += ((k >> (i - 1)) & 1);
}
return re;
}

1. 位运算的简单应用
表达式
位运算等价
x+y
(x|y)+(x&y)
x-y
(x|~y)-(~x&y)
x^y
(x|y)-(x&y)
x|y
(x&~y)+y
x&y
(~x|y)-~x
x==y
(x-y|y-x)
x!=y
x-y|y-x
x< y
(x-y)^((x^y)&((x-y)^x))
x< y
(~x&y)|((~x|y)&(x-y)) //无符号x,y比较
x<=y
(~x|y)&((x^y)|~(y-x)) //无符号x,y比较
2. 判断奇偶
只要根据最未位是0还是1来决定，为0就是偶数，为1就是奇数。因此可以用if (a & 1 == 0)代替if (a % 2 == 0)来判断a是不是偶数。可以得到如下代码：
1
bool isEven(int n) {
2
if (n & 1) {

3
return true;
4
} else {

5
return false;
6
}

7
}
3. 不使用第三变量的两数交换
1
void swap(int &a, int &b) {
2

3
if (a != b) {
4
a ^= b;

5
b ^= a;
6
a ^= b;

7
}
8
}
可以这样理解：
1）a^=b 即a=(a^b);
2）b^=a 即b=b^(a^b)，由于^运算满足交换律，b^(a^b)=b^b^a。由于一个数和自己异或的结果为0并且任何数与0异或都会不变的，所以此时b被赋上了a的值。
3）a^=b 就是a=a^b，由于前面二步可知a=(a^b)，b=a，所以a=a^b即a=(a^b)^a。故a会被赋上b的值。
再来个实例说明下以加深印象。int a = 13, b = 6;
a的二进制为 13=8+4+1=1101(二进制)
b的二进制为 6=4+2=110(二进制)
第一步 a^=b a = 1101 ^ 110 = 1011;
第二步 b^=a b = 110 ^ 1011 = 1101;即b=13
第三步 a^=b a = 1011 ^ 1101 = 110;即a=6
4. 改变符号
变换符号就是正数变成负数，负数变成正数。可以利用求补码的方法（按位取反+1）来 处理。
如对于-11和11，可以通过下面的变换方法将-11变成11
1111 0101(二进制) –取反-> 0000 1010(二进制) –加1-> 0000 1011(二进制)
同样可以这样的将11变成-11
0000 1011(二进制) –取反-> 0000 1010(二进制) –加1-> 1111 0101(二进制)
可以得到如下代码：
1
int changeSign(int n) {
2
return ~n + 1;

3
}
5. 取绝对值
对于任何数，与0异或都会保持不变，与-1即0xFFFFFFFF异或就相当于取反,因此，a与i异或后再减i（因为i为0或-1，所以减i即是要么加0要么加1）也可以得到绝对值因此可以得 到如下代码：
1
int abs(int n) {
2
return (n ^ (n >> 31)) - (n >> 31);

3
}
6. 高低位互换
给出一个32位的无符号整数。称这个二进制数的前16位为“高位”，后16位为“低位”。现在写一程序将它的高低位交换。例如，数0x1234ABCD用二进制表示为：
0001 0010 0011 0100 1010 1011 1100 1101
将它的高低位进行交换，我们得到了一个新的二进制数：
1010 1011 1100 1101 0001 0010 0011 0100
它即是0xABCD1234。
这个问题用位操作解决起来非常方便，设x=0x1234ABCD由于x为无符号数，右移时会执行逻辑右移即高位补0，因此x右移16位将得到0000 0000 0000 0000 0001 0010 0011 0100。而x左移8位将得到0000 0000 0000 0000 1010 1011 1100 1101。可以发现只要将x>>16与x<<16这两个数相或就可以得到结果。代码如下
1
int exchangeBits(unsigned int n) {
2
return (n >> 16) | (n << 16);

3
}
7. 二进制逆序
我们知道如何对字符串求逆序，现在要求计算二进制的逆序，如数34520用二进制表示为：10000110 11011000 00000000 00000000
将它逆序，我们得到了一个新的二进制数：00000000 00000000 00011011 01100001
它即是十进制的7009。
回顾下字符串的逆序的方法，可以从字符串的首尾开始，依次交换两端的数据。在二进制逆序我们也可以用这种方法，但运用位操作的高低位交换来处理二进制逆序将会得到更简洁的方法。类似于归并排序的分组处理，可以通过下面4步得到32位数据的二进制逆序：
第一步：每2位为一组，组内高低位交换
00 00 00 00 00 00 00 00 10 00 01 10 11 01 10 00
→ 00 00 00 00 00 00 00 00 01 00 10 01 11 10 01 00
第二步：每4位为一组，组内高低位交换
0000 0000 0000 0000 0100 1001 1110 0100
→ 0000 0000 0000 0000 0001 0110 1011 0001
第三步：每8位为一组，组内高低位交换
00000000 00000000 00010110 10110001
→ 00000000 00000000 01100001 00011011
第四步：每16位为一组，组内高低位交换
0000000000000000 0110000100011011
→ 0110000100011011 0000000000000000
对第一步，可以依次取出每2位作一组，再组内高低位交换，这样有点麻烦，下面介绍一种非常有技巧的 方法。先分别取10000110 11011000的奇数位和偶数位，空位以下划线表示。
原 数 00000000 00000000 10000110 11011000
奇数位 0_0_0_0_ 0_0_0_0_ 1_0_0_1_ 1_0_1_0_
偶数位 _0_0_0_ 0 _0_0_0_ 0 _0_0_1_0 _1_1_0_0
将下划线用0填充，可得
原 数 00000000 00000000 10000110 11011000
奇数位 00000000 00000000 10000010 10001000
偶数位 00000000 00000000 00000100 01010000
再将奇数位右移一位，偶数位左移一位，此时将这两个数据相与即可以达到奇偶位上数据交换的效果了。
原 数 00000000 00000000 10000110 11011000
奇数位右移 00000000 00000000 01000011 01101100
偶数位左移 00000000 00000000 00001000 10100000
相或得到 00000000 00000000 01001000 11100100
可以看出，结果完全达到了奇偶位的数据交换，再来考虑代码的实现——
取x的奇数位并将偶数位用0填充用代码实现就是x & 0xAAAAAAAA
取x的偶数位并将奇数位用0填充用代码实现就是x & 0×55555555
因此，第一步就用代码实现就是：
x = ((x & 0xAAAAAAAA) >> 1) | ((x & 0×55555555) << 1);
类似可以得到如下代码：
1
int revertBits(unsigned int n) {
2
n = ((n & 0xAAAAAAAA) >> 1 ) | ((n & 0x55555555) << 1);

3
n = ((n & 0xCCCCCCCC) >> 2 ) | ((n & 0x33333333) << 2);
4
n = ((n & 0xF0F0F0F0) >> 4 ) | ((n & 0x0F0F0F0F) << 4);

5
n = ((n & 0xFF00FF00) >> 8 ) | ((n & 0x00FF00FF) << 8);
6
n = ((n & 0xFFFF0000) >> 16 ) | ((n & 0x0000FFFF) << 16);

7

8
return n;

9
}
8. 32位整数前导零的个数
01
int preZero(unsigned int n) {
02
int count = 0;

03

04
if (n == 0)

05
return(32);
06
if ((n >> 16) == 0)

07
count = count + 16; n = n << 16;
08
if ((n >> 24) == 0)

09
count = count + 8; n = n << 8;
10
if ((n >> 28) == 0)

11
count = count + 4; n = n << 4;
12
if ((n >> 30) == 0)

13
count = count + 2; n = n << 2;
14
if ((n >> 31) == 0)

15
count = count + 1; n = n << 1;
16

17
return count;
18
}
9. 二进制中1的个数
方法1：
考虑到n-1会把n的二进制表示中最低位的1置0并把其后的所有0置1，同时不改变此位置前的所有位，那么n&(n-1)即可消除这个最低位的1。这样便有了比顺序枚举所有位更快的算法：循环消除最低位的1，循环次数即所求1的个数。此算法的时间复杂度为O(n的二进制表示中的1的个数)，最坏情况下的复杂度O(n的二进制表示的总位数)。
1
int count1(unsigned int n) {
2
int count = 0;

3
while(n) {
4
n &= (n - 1);

5
count++;
6
}

7
return count;
8
}
方法2：
通过下面四步来计算其二进制中1的个数二进制中1的个数。
第一步：每2位为一组，组内高低位相加
00 00 00 00 00 00 00 00 10 00 01 10 11 01 10 00
→ 00 00 00 00 00 00 00 00 01 00 01 01 10 01 01 00
第二步：每4位为一组，组内高低位相加
0000 0000 0000 0000 0100 0101 1001 0100
→ 0000 0000 0000 0000 0001 0010 0011 0001
第三步：每8位为一组，组内高低位相加
00000000 00000000 00010010 00110001
→ 00000000 00000000 00000011 00000100
第四步：每16位为一组，组内高低位相加
0000000000000000 0000001100000100
→ 0000000000000000 0000000000000111
代码如下：
1
int count1_2(unsigned int n) {
2
n = ((n & 0xAAAAAAAA) >> 1 ) + (n & 0x55555555);

3
n = ((n & 0xCCCCCCCC) >> 2 ) + (n & 0x33333333);
4
n = ((n & 0xF0F0F0F0) >> 4 ) + (n & 0x0F0F0F0F);

5
n = ((n & 0xFF00FF00) >> 8 ) + (n & 0x00FF00FF);
6
n = ((n & 0xFFFF0000) >> 16 ) + (n & 0x0000FFFF);

7
return n;
8
}