位运算技巧集

一般用0xfffffff这种16位数，代替32位二进制数；Java中的幂指数运算不能是^ ,这个符号代表的是异或运算符；&|~^ 与或非异或两个大于号 向右移位运算一般可以通过先将需要处理的数字变为二进制数，在观察数字，运算和最终结果之间和关系。如果需要处理和数字有两个，可以观察两个数字的组合又什么规律。比如，通过拼接，异或，与运算得出某个数，推导这个数和最终结果有什么关系。 for(i:=31;i>=0;i--){ 1<<i; } 0010000 0001000 0000100 0000010 0000001 以上代码可以用来按位比较对应的bit，最大不超过32bit,因为每次循环对1进行移位操作后结果的值如上。 n = 100000 n-1 = 011111 n & n-1 = 0 n = 101000 n-1 = 100111 n & n-1 = 100000 所以只要在n不为0的时候每次对n与n-1进行&操作就可以消掉最右侧的一个1。左移一位乘2，右移一位除2 。特殊数字（其实很多(lll￢ω￢)·······）奇数位偶数位啥的有需要自己算吧

0x55555555 01010101010101010101010101010101

0x33333333 00110011001100110011001100110011

0x0f0f0f0f 00001111000011110000111100001111

这0和1还不一边长 (lll￢ω￢)

前n位和后n位进行或操作可前后换位，这要建立在其他位都是0的情况下才有效，这样才能确实保证是和0操作，否则其它位移动后和0或，又多一位。(非常经典的高低位交换) a = (a >> 8) | (a << 8);

Java 没有无符号数哦

位操作进行二进制逆序将无符号数的二进制表示进行逆序，求取逆序后的结果。

如数34520的二进制表示： 10000110 11011000 逆序后则为： 00011011 01100001

它的十进制为7009在字符串逆序过程中，可以从字符串的首尾开始，依次交换两端的数据。在二进制中使用位的高低位交换会更方便进行处理，这里我们分组进行多步处理。

归并： （右移n位|左移n位） 下面这个方法，找数字是非常繁琐的，底下有更好的。

第一步:以每 2 位为一组，组内进行高低位交换

交换前： 10 00 01 10 11 01 10 00 交换后： 01 00 10 01 11 10 01 00

第二步：在上面的基础上，以每 4 位为 1 组，组内高低位进行交换

交换前： 0100 1001 1110 0100 交换后： 0001 0110 1011 0001

第三步：以每 8 位为一组，组内高低位进行交换

交换前： 00010110 10110001 交换后： 01100001 00011011

第四步：以每16位为一组，组内高低位进行交换

交换前： 0110000100011011 交换后： 0001101101100001

对于上面的第一步，依次以 2 位作为一组，再进行组内高低位交换，这样处理起来比较繁琐，下面介绍另外一种方法进行处理。

先分别取原数 10000110 11011000 的奇数位和偶数位，将空余位用 0 填充：原数： 10000110 11011000 奇数位： 10000010 10001000 偶数位： 00000100 01010000 再将奇数位右移一位，偶数位左移一位，此时将两个数据相或即可以达到奇偶位上数据交换的效果：

原数： 10000110 11011000 奇数位右移一位： 0 10000010 1000100 偶数位左移一位：0000100 01010000 0 两数相或得到： 01001001 11100100

上面的方法用位操作可以表示为： 取a的奇数位并用 0 进行填充可以表示为： a & 0xAAAA 取a的偶数为并用 0 进行填充可以表示为： a & 0x5555

因此，上面的第一步可以表示为： a = ((a & 0xAAAA) >> 1) | ((a & 0x5555) << 1) 同理，可以得到其第二、三和四步为： a = ((a & 0xCCCC) >> 2) | ((a & 0x3333) << 2) a = ((a & 0xF0F0) >> 4) | ((a & 0x0F0F) << 4) a = ((a & 0xFF00) >> 8) | ((a & 0x00FF) << 8) 因此整个操作为：unsigned short a = 34520;

a = ((a & 0xAAAA) >> 1) | ((a & 0x5555) << 1); a = ((a & 0xCCCC) >> 2) | ((a & 0x3333) << 2); a = ((a & 0xF0F0) >> 4) | ((a & 0x0F0F) << 4); a = ((a & 0xFF00) >> 8) | ((a & 0x00FF) << 8); x^x=0; x^0=x; 数组中，只有一个数出现一次，剩下都出现两次，找出出现一次的数if(n & 1 == 1) 判断奇数偶数a ^ b 无进位加法a & b 进位标志

Java中均为补码

正数的原码、反码、补码相同。

负数的反码是原码除最高位的取反，补码是反码+1