java经典位运算实例1) int型变量循环左移k次，即a=a >16-k (设sizeof(int)=16) (2) int型变量a循环右移k次，即a=a>>k |a >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;...
1) int型变量循环左移k次，即a=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 (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 int cmp( int x, int y ) { return (x>y)-(x-y) ; } doz=x-y, x>=y; 0, 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)<>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<> ( 1<>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 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，就如上面的
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
，就可以将那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>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> 上面关于标志值的操作就介绍完毕。其实在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 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>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> 好啦，够长了，就停止吧。在最后再给大家一段代码，是用来看看对象在内存中的位值的。可以看看。 string bitsOfUChar(unsigned char c) { const int numOfBitsInUChar = 8; unsigned int mask = (1<<7); string result(8, '0'); for (size_t i=0; i>= 1; } return result; } template string bitsInMemory(const T& obj) { int sizeOfObj = sizeof(obj); unsigned char* pt = (unsigned char*)&obj; string result; for (size_t i=0; i
本文档为【java经典位运算实例】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483