经典的位运算实例

古城微笑少年丶 2022-02-15 13:29 269阅读 0赞

1) int型变量循环左移k次，即a=a < <k |a>>16-k (设sizeof(int)=16)  
(2) int型变量a循环右移k次，即a=a>>k |a < <16-k (设sizeof(int)=16)  
(3)整数的平均值  
对于两个整数x,y，如果用 (x+y)/2 求平均值，会产生溢出，因为 x+y 可能会大于INT\_MAX，但是我们知道它们的平均值是肯定不会溢出的，我们用如下算法：  
int average(int x, int y) //返回X,Y 的平均值  
\{  
return (x&y)+((x^y)>>1);  
\}  
(4)判断一个整数是不是2的幂,对于一个数 x >= 0，判断他是不是2的幂  
boolean power2(int x)  
\{  
return ((x&(x-1))==0)&&(x!=0)；  
\}  
(5)不用temp交换两个整数  
void swap(int x , int y)  
\{  
x ^= y;  
y ^= x;  
x ^= y;  
\}  
(6)计算绝对值  
int abs( int x )  
\{  
int y ;  
y = x >> 31 ;  
return (x^y)-y ; //or: (x+y)^y  
\}  
(7)取模运算转化成位运算 (在不产生溢出的情况下)  
a % (2^n) 等价于 a & (2^n - 1)  
(8)乘法运算转化成位运算 (在不产生溢出的情况下)  
a \* (2^n) 等价于 a < < n  
(9)除法运算转化成位运算 (在不产生溢出的情况下)  
a / (2^n) 等价于 a>> n  
例: 12/8 == 12>>3

PS:

<table style="color:rgb(51,51,51); margin:0px; padding:0px; font-family:Arial,宋体,sans-serif; font-size:16px; line-height:30px; text-align:left; table-layout:fixed"> 
 <tbody style="margin:0px; padding:0px"> 
  <tr style="margin:0px; padding:0px"> 
   <td style="margin:0px; padding:0px"> 
    <div style="margin:0px; padding:0px">
      用移位实现乘除法运算&nbsp; 
     <br style="margin:0px; padding:0px"> 　　a=a*4;&nbsp; 
     <br style="margin:0px; padding:0px"> 　　b=b/4;&nbsp; 
     <br style="margin:0px; padding:0px"> 　　 
     <a href="http://www.haogongju.net/tag/%E5%8F%AF%E4%BB%A5" title="可以" style="color:rgb(51,51,51); margin:0px; padding:0px; text-decoration:none" rel="nofollow">可以</a>改为：&nbsp; 
     <br style="margin:0px; padding:0px"> 　　a=a&lt;&lt;2;&nbsp; 
     <br style="margin:0px; padding:0px"> 　　b=b&gt;&gt;2;&nbsp; 
     <br style="margin:0px; padding:0px"> 　　 
     <span style="margin:0px; padding:0px">说明：</span>&nbsp; 
     <br style="margin:0px; padding:0px"> 　　除2 = 右移1位 乘2 = 左移1位&nbsp; 
     <br style="margin:0px; padding:0px"> 　　除4 = 右移2位 乘4 = 左移2位&nbsp; 
     <br style="margin:0px; padding:0px"> 　　除8 = 右移3位 乘8 = 左移3位&nbsp; 
     <br style="margin:0px; padding:0px"> 　　... ...&nbsp; 
     <br style="margin:0px; padding:0px"> 　　通常如果需要乘以或除以2的n次方 
     <span style="margin:0px; padding:0px">，</span>都可以用移位的 
     <a href="http://www.haogongju.net/tag/%E6%96%B9%E6%B3%95" title="方法" style="color:rgb(51,51,51); margin:0px; padding:0px; text-decoration:none" rel="nofollow">方法</a>代替。&nbsp; 
     <br style="margin:0px; padding:0px"> 　　大部分的C编译器,用移位的方法得到代码比调用乘除法子程序生成的代码效率高。&nbsp; 
     <br style="margin:0px; padding:0px"> 　　实际上，只要是乘以或除以一个整数，均可以用移位的方法得到结果，如：&nbsp; 
     <br style="margin:0px; padding:0px"> 　　a=a*9&nbsp; 
     <br style="margin:0px; padding:0px"> 　　 
     <a href="http://www.haogongju.net/tag/%E5%88%86%E6%9E%90" title="分析" style="color:rgb(51,51,51); margin:0px; padding:0px; text-decoration:none" rel="nofollow">分析</a>a*9可以拆分成a*(8+1)即a*8+a*1, 因此可以改为： a=(a&lt;&lt;3)+a&nbsp; 
     <br style="margin:0px; padding:0px"> 　　a=a*7&nbsp; 
     <br style="margin:0px; padding:0px"> 　　分析a*7可以拆分成a*(8-1)即a*8-a*1, 因此可以改为： a=(a&lt;&lt;3)-a&nbsp; 
     <br style="margin:0px; padding:0px"> 　　关于除法读者可以类推, 此略.&nbsp; 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

(10) a % 2 等价于 a & 1  
(11) if (x == a) x= b;  
　　 else x= a;  
　　 等价于 x= a ^ b ^ x;  
(12) x 的 相反数 表示为 (~x+1)

(13)求从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;  
\}  
(14)  
/\*将32位数分解为4个8位数处理后再合成32位数返回\*/  
DWORD GetDW(DWORD dw)  
\{  
DWORD dwRet=0;  
if (dw!=0)  
\{  
BYTE b1=(dw>>24)&0xff,b2=(dw>>16)&0xff,b3=(dw>>8)&0xff,b4=dw&0xff;  
//分别处理 b1,b2,b3,b4  
dwRet=b1;  
dwRet=(dwRet<<8)+b2;  
dwRet=(dwRet<<8)+b3;  
dwRet=(dwRet<<8)+b4;

return dwRet;  
\}  
else\{  
return 0;  
\}  
\}  
  
  
检测一个无符号数是不为2^n-1(^为幂)： x&(x+1)  
  
将最右侧0位改为1位： x | (x+1)  
  
二进制补码运算公式：  
\-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比较  
  
  
使用位运算的无分支代码：  
  
计算绝对值  
int abs( int x )  
\{  
int y ;  
y = x >> 31 ;  
return (x^y)-y ;//or: (x+y)^y  
\}  
  
符号函数：sign(x) = -1, x<0; 0, x == 0 ; 1, x > 0  
int sign(int x)  
\{  
return (x>>31) | (unsigned(-x))>>31 ;//x=-2^31时失败(^为幂)  
\}  
  
三值比较：cmp(x,y) = -1, x<y; 0, x==y; 1, x > y  
int cmp( int x, int y )  
\{  
return (x>y)-(x-y) ;  
\}  
  
doz=x-y, x>=y; 0, x<y  
int doz(int x, int y )  
\{  
int d ;  
d = x-y ;  
return d & ((~(d^((x^y)&(d^x))))>>31) ;  
\}  
  
int max(int x, int y )  
\{  
int m ;  
m = (x-y)>>31 ;  
return y & m | x & ~m ;  
\}  
  
不使用第三方交换x,y:  
1.x ^= y ; y ^= x ; x ^= y ;  
2.x = x+y ; y = x-y ; x = x-y ;  
3.x = x-y ; y = y+x ; x = y-x ;  
4.x = y-x ; x = y-x ; x = x+y ;  
  
双值交换:x = a, x==b; b, x==a//常规编码为x = x==a ? b :a ;  
1.x = a+b-x ;  
2.x = a^b^x ;  
  
下舍入到2的k次方的倍数:  
1.x & ((-1)<<k)  
2.(((unsigned)x)>>k)<<k  
上舍入：  
1. t = (1<<k)-1 ; x = (x+t)&~t ;  
2.t = (-1)<<k ; x = (x-t-1)&t ;  
  
位计数,统计1位的数量：  
1.  
int pop(unsigned x)  
\{  
x = x-((x>>1)&0x55555555) ;  
x = (x&0x33333333) + ((x>>2) & 0x33333333 ) ;  
x = (x+(x>>4)) & 0x0f0f0f0f ;  
x = x + (x>>8) ;  
x = x + (x>>16) ;  
return x & 0x0000003f ;  
\}  
2.  
int pop(unsigned x) \{  
static char table\[256\] = \{ 0,1,1,2, 1,2,2,3, ...., 6,7,7,8 \} ;  
return table\[x&0xff\]+table\[(x>>8)&0xff\]+table\[(x>>16)&0xff\]+table\[(x>>24)\] ;  
\}  
  
奇偶性计算:  
x = x ^ ( x>>1 ) ;  
x = x ^ ( x>>2 ) ;  
x = x ^ ( x>>4 ) ;  
x = x ^ ( x>>8 ) ;  
x = x ^ ( x>>16 ) ;  
结果中位于x最低位，对无符号x,结果的第i位是原数第i位到最左侧位的奇偶性  
  
  
位反转：  
unsigned rev(unsigned x)  
\{  
x = (x & 0x55555555) << 1 | (x>>1) & 0x55555555 ;  
x = (x & 0x33333333) << 2 | (x>>2) & 0x33333333 ;  
x = (x & 0x0f0f0f0f) << 4 | (x>>4) & 0x0f0f0f0f ;  
x = (x<<24) | ((x&0xff00)<<8) | ((x>>8) & 0xff00) | (x>>24) ;  
return x ;  
\}  
  
递增位反转后的数：  
unsigned inc\_r(unsigned x)  
\{  
unsigned m = 0x80000000 ;  
x ^= m ;  
if( (int)x >= 0 )  
do \{ m >>= 1 ; x ^= m ; \} while( x < m ) ;  
return x ;  
\}  
  
混选位：  
abcd efgh ijkl mnop ABCD EFGH IJKL MNOP->aAbB cCdD eEfF gGhH iIjJ kKlL mMnN oOpP  
unsigned ps(unsigned x)  
\{  
unsigned t ;  
t = (x ^ (x>>8)) & 0x0000ff00; x = x ^ t ^ (t<<8) ;  
t = (x ^ (x>>4)) & 0x00f000f0; x = x ^ t ^ (t<<4) ;  
t = (x ^ (x>>2)) & 0x0c0c0c0c; x = x ^ t ^ (t<<2) ;  
t = (x ^ (x>>1)) & 0x22222222; x = x ^ t ^ (t<<1) ;  
return x ;  
\}  
  
位压缩：  
选择并右移字x中对应于掩码m的1位的位,如：compress(abcdefgh,01010101)=0000bdfh  
compress\_left(x,m)操作与此类似，但结果位在左边: bdfh0000.  
unsigned compress(unsigned x, unsigned m)  
\{  
unsigned mk, mp, mv, t ;  
int i ;  
  
x &= m ;  
mk = ~m << 1 ;  
for( i = 0 ; i < 5 ; ++i ) \{  
mp = mk ^ ( mk << 1) ;  
mp ^= ( mp << 2 ) ;  
mp ^= ( mp << 4 ) ;  
mp ^= ( mp << 8 ) ;  
mp ^= ( mp << 16 ) ;  
mv = mp & m ;  
m = m ^ mv | (mv >> (1<<i) ) ;  
t = x & mv ;  
x = x ^ t | ( t >> ( 1<<i) ) ;  
mk = mk & ~mp ;  
\}  
return x ;  
\}  
  
  
位置换：  
用32个5位数表示从最低位开始的位的目标位置，结果是一个32\*5的位矩阵，  
将该矩阵沿次对角线转置后用5个32位字p\[5\]存放。  
SAG(x,m) = compress\_left(x,m) | compress(x,~m) ;  
准备工作：  
void init( unsigned \*p ) \{  
p\[1\] = SAG( p\[1\], p\[0\] ) ;  
p\[2\] = SAG( SAG( p\[2\], p\[0\]), p\[1\] ) ;  
p\[3\] = SAG( SAG( SAG( p\[3\], p\[0\] ), p\[1\]), p\[2\] ) ;  
p\[4\] = SAG( SAG( SAG( SAG( p\[4\], p\[0\] ), p\[1\]) ,p\[2\]), p\[3\] ) ;  
\}  
实际置换：  
int rep( unsigned x ) \{  
x = SAG(x,p\[0\]);  
x = SAG(x,p\[1\]);  
x = SAG(x,p\[2\]);  
x = SAG(x,p\[3\]);  
x = SAG(x,p\[4\]);  
return x ;  
\}  
  
二进制码到GRAY码的转换:  
unsigned B2G(unsigned B )  
\{  
return B ^ (B>>1) ;  
\}  
GRAY码到二进制码:  
unsigned G2B(unsigned G)  
\{  
unsigned B ;  
B = G ^ (G>>1) ;  
B = G ^ (G>>2) ;  
B = G ^ (G>>4) ;  
B = G ^ (G>>8) ;  
B = G ^ (G>>16) ;  
return B ;  
\}  
  
找出最左0字节的位置:  
int zbytel( unsigned x )  
\{  
static cahr table\[16\] = \{ 4,3,2,2, 1,1,1,1, 0,0,0,0, 0,0,0,0 \} ;  
unsigned y ;  
y = (x&0x7f7f7f7f) + 0x7f7f7f7f ;  
y = ~(y|x|0x7f7f7f7f) ;  
return table\[y\*0x00204081 >> 28\] ;//乘法可用移位和加完成  
\}

C\\C++支持比较低阶的位运算，在是众人皆知的了。每本C\\C++的教科书都会说到这部分的内容，不过都很简略，我想会有很多人不知道位运算用在什么地方。这个帖子就简略说说位运算的用处，更进一步的用法要大家自己去体会。而主要说的是操作标志值方面。

/\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/

\#define BTI\_MSK(bit) (1 << (bit))  
\#define BIT\_SET(x,bit) ((x) |= BTI\_MSK (bit))  
\#define BIT\_CLR(x,bit) ((x) &= ~BTI\_MSK (bit))  
\#define BIT\_TST(x,bit) ((x) & BTI\_MSK (bit))

/\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/

考虑一个事物、一个系统、或者一个程序可能会出现一种或者几种状态。为了在不同的状态下，作出不同的行为，你可以设立一些标志值，再根据标志值来做判断。比如C++的文件流，你就可以设定一些标志值，ios::app, ios::ate, ios::binary, ios::in, ios::out, ios::trunc，并且可以将它用|组合起来创建一个恰当的文件流。你可能会将这些标志值定义为bool类型，不过这样要是设置的标志值一多，就会很浪费空间。  
  
而假如定义一个整型数值，unsigned int flags; 在现在的系统，flags应该是32位, 用1,2,3....32将位进行编号，我们可以进行这样的判断, 当位1取1时，表示用读方式打开文件，当位2取1时，表示用写方式打开文件，当位3取1时，用二进制方式打开文件....因为flags有32位，就可以设置32个不同的状态值，也相当于32个bool类型。这样一方面省了空间, 另一方面也多了个好处，就是如前面所说的，可以将标志值组合起来。  
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>  
  
好啦，上面有点不清不楚的。下面看看到底怎么操作这些标志值。  
设想C++的类ios这样定义, 其实没有这个类，只有ios\_basic类，typedef basic\_ios<char> ios;  
  
class ios  
\{  
public:  
enum \{ app = 0x0001, ate = 0x0002, binary = 0x0004,  
in = 0x0008, out = 0x0010, trunc = 0x0020 \};  
....  
private:  
unsigned int flags;  
\};  
  
注意上面enum语句中，每一个数值只有1位是1，其余是0，这个很重要，你可以将它化成2进制看看。  
  
现在将flags相应的位设置为1, 可以这样做 flags |= app。这个等于flags = flags | app, 为什么呢? app只有1位是1，其余是0，因为0 | 1 = 0， 0 | 0 = 0， 这样0对应的位是不变的。而1 | 1 = 1, 1 | 0 = 1, 1对应的位不论原来是什么状态，都一定为1。如果想要将几个位都设置为1，可以这样做 flags |= (app | ate | binary)。因为每个enum常数各有一位为1, 与运算之后就有3位为1，就如上面的分析，就可以将那3位都设置为1, 其余位不变。这个就是标志可以组合起来用的原因。也可以用+组合起来，原因在于(下面的数字是2进制)0001 + 0010 + 0100 = 0111 跟与运算结果一样。不过不提倡用+, 考虑(app | ate | binary)要是我不小心写多了个标志值，(app | ate | ate | binary)结果还是正确的，如果用+的话，就会产生进位，结果就会错误。通常我们不知道原先已经组合了多少个标志值了，用或运算会安全。  
  
现在将flags对应的位设置为0, 可以这样做 flags &= ~app。相当于 flags = flags & (~app). app取反之后，只有1位是0，其余是1，做与运算之后，1对应的位并不会改变，0对应的为不管原来是1是0，都肯定为0，这样就将对应的位设置了0。同样同时设置几个标志位可以这样做，flags &= ~(app | ate | binary)。  
  
现在将flags对应的位，如果是1就变成0，如果是0就变成1，可以这样做 flags ^= app。同时设置几个标志位可以写成 flags ^= (app | ate | binary)。不再做分析了，不然就太罗嗦了。不过也给大家一个例子，你查查Ascii表，会发现对应的大小写字母是相差倒数第6位，可以用这样的函数统一的将大写变成小写，小写变成大写。  
void xchgUppLow(string& letters)  
\{  
const unsigned int mask = (1<<5);  
  
for (size\_t i=0; i<letters.length(); i++)  
letters\[i\] ^= mask;  
\}  
前提是输入的string一定要全是字母, 而要想是操作字母，可以在原来基础上加个判断。  
  
好啦，上面已经可以设置flags的对应位值了，要是判断呢？可以这样写 if (flags & app) 这样可以判断对应的位值是否为1, 因为C\\C++语言中非0就真。app只有一位是1，其余是0，如果, flags的对应位也是0，在与操作下就得到结果0，反之非0，这样就可以判断标志位了。  
  
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>  
上面关于标志值的操作就介绍完毕。其实在C++中已经有了个bitset了，没有必要去自己进行低阶的位运算，上面的四个操作在bitset中分别叫做set, reset, flip, test。不过在C中，这样的代码还很常见, 反正知道多点也没有坏处。  
  
用 windows API 编程，你也经常会碰到这样的标志值，要互相组合，可以用|, 也可以用+(只是建议用|，理由上面说了). 它的标志值也是这样定义的，不过用\#define  
\#define WS\_BORDER 0x0001  
\#define WS\_CAPTION 0x0002  
......  
当初我就是想不明白为什么可以用|或者用+来组合，现在知道了。  
  
(注：上面出现的数字是我自己作的，到底实际怎么定义其实没有关系，只要保证只有一位是1，其余是0就可以的了. 因为编程的时候用的是常量值，没有人这样笨去直接用数值的)  
  
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>  
其实，位运算还有很多用处。比如移位相当于乘除2的幂数(不过通常编译器也将乘除2的幂数优化成汇编的移位指令，所以没有必要不要这样卖弄了。汇编的移位指令有两组，分别针对有符号和无符号的, 我猜想在C\\C++的同一移位运算针对有符号整数和无符号整数的不同，会根据情况编译成不同的汇编移位指令，不过没有去证实), 其实移位更用得多的地方是去构造一个掩码, 比如上面的mask = (1<<5);  
  
还有&运算，有时候可以用来求余数。比如 value & (1<<4 - 1) 这相当于将value的高位全变成0了，效果等于 value % 8.  
  
还有值得一提的是^运算，它有个很特殊的性质。比如 A ^= B, 变成另一个数，跟着再执行A ^= B，又变回原来的数了，不信你可以列真值表或者化简逻辑式看看。就因为这个性质，^有很多用途。比如加密，你将原文看成A, 用同一个B异或一次，就相当于加密，跟着在用B异或一次，相当于解密。不过这样是很容易破解就是了。要是一个B不够，还可以加个C, 比如A ^= B, A ^= C, A ^= C, A ^= B, 恢复原状。  
  
下面一个小程序，用异或交换两个数字。  
int x = 3;  
int y = 4;  
  
x ^= y;  
y ^= x;  
x ^= y;  
  
其实何止交换数字，连交换对象也可以的  
template <typename T>  
void swap(T& obj1, T& obj2)  
\{  
const int sizeOfObj = sizeof(T);  
char\* pt1 = (char\*)&obj1;  
char\* pt2 = (char\*)&obj2;  
  
for (size\_t i=0; i<sizeOfObj; i++)  
\{  
pt1\[i\] ^= pt2\[i\];  
pt2\[i\] ^= pt1\[i\];  
pt1\[i\] ^= pt2\[i\];  
\}  
\}  
  
还有异或操作还可以用在图象的光栅操作。我们知道，颜色也是用二进制来表示的，对颜色进行不同的位运算，就可以得到不同的光栅。因为异或的特殊性质，我们用异或操作的光栅画了副图，跟着再在原来的地方画一次，那副图就刷除了。这样可以用来显示动画而不用保存原来的画像信息。以前我写过个双人的贪食蛇，就用了异或光栅。因为背景色是白色的，也就是全1，作A ^ 1 = A, 所以用画刷画一次是画了设定的颜色，再画一次就恢复。最有趣的是两蛇相交的时候，颜色也会作异或叠加，产生一种新的颜色了，离开的时候也会自动恢复。  
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>  
好啦，够长了，就停止吧。在最后再给大家一段代码，是用来看看对象在内存中的位值的。可以看看。  
string bitsOfUChar(unsigned char c)  
\{  
const int numOfBitsInUChar = 8;  
unsigned int mask = (1<<7);  
string result(8, '0');  
  
for (size\_t i=0; i<numOfBitsInUChar; i++)  
\{  
if ( mask & c)  
result\[i\] = '1';  
  
mask >>= 1;  
\}  
  
return result;  
\}  
  
template <typename T>  
string bitsInMemory(const T& obj)  
\{  
int sizeOfObj = sizeof(obj);  
unsigned char\* pt = (unsigned char\*)&obj;  
string result;  
  
for (size\_t i=0; i<sizeOfObj; i++)  
\{  
result += bitsOfUChar(pt\[i\]);  
result += ' ';  
\}  
  
return result;  
\}  
  
比如bitsInMemory(12)，会输出00001100 00000000 00000000 00000000, 我就知道我自己的机器是小尾顺序的了。