位运算的应用

注意：任何语言中二进制是没有显示的表示的，所以如果需要使用二进制则只能用10进制（想成2进制），或者用string
         for(int i=0;i<32;i++){
	Integer a = i|(1<<5);  //100001  ---这里前面5位表示需要增加的东西哦，1<<5，1移动5位，就是移到第六位上
          }
			
  String[] b = Integer.toBinaryString(a).substring(1).split("");
从b[1]----b[5]是真正需要的东西，b[0]为空，因为split("")的原因,这里substring(1)可是把首位截去了哈。。。。

1。与运算
两个二进位均为1时，结果位才为1 ，否则为0

把a 的高八位清 0 ， 保留低八位， 可作 a&255 运算 ( 255 的二进制数为0000000011111111)。

应用;
 a. 清零特定位 (mask中特定位置0，其它位为1，s=s&mask)
 b. 取某数中指定位的值 (mask中特定位置1，其它位为0，s=s&mask)
&就像一个橡皮，擦掉0的位，提取1的位
c.a&b<<1 可以看成进位产生的值


2。按位或运算
00001001|00000101
00001101 (十进制为13)可见9|5=13

常用来将源操作数某些位置1，其它位不变。 (mask中特定位置1，其它位为0 s=s|mask) 
|想一根棍子，插入1用的



3。按位异或运算
00001001^00000101 00001100 (十进制为12)
含义是：不进位的加法，又称为半加运算; 1使得特定位置取反
异或运算最本质的意思是找出a和b的不同位，不同位为1

助记：异，1或

应用：
a. 使特定位的值取反 (mask中特定位置1，其它位为0 s=s^mask)
b. 不引入第三变量，交换两个变量的值
c.与自己计算值为0； a^a=0;

4。求反运算

~(0000000000001001)结果为：1111111111110110

5。左移运算符“<<”

其值相当于乘2 。
6。右移运算 ">>"

其值相当于除2。
'下面是从牛逼博客上抄的。。。值得学习'
位运算应用口诀
清零取数要用与，插入某数要用或
若要取反和交换，轻轻松松用异或
  
移位运算
要点 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,b)
 a = a^b^a  //先去到a,b的中间值，然后消去a
 b = a^b^b  //先去到a,b的中间值，然后消去b
以上是简易思路，正确的思路是：先寻找 a和b的不同之处，那么a变成b也就是把他们的相同之处不变，不同之处取反。
异或-----异 和  或：  异：找出不同的地方并置为1
                    或： 碰到1就取反  
这是一个运算符，但可以从两个维度来理解他

应用举例 


(1) 判断int型变量a是奇数还是偶数                      
a& 1    = 0 偶数 （与1相加能进位说明个位是1,个位为0）
a& 1    = 1 奇数 （与1相加不能进位说明个位是0,个位为1）
或者
a&1
判断奇偶也就是判断个位上的数
a = 10010001
b=1
a&b = 0 != b 说明第1位因为是1，所以可进位，所以a的值改变
b=10  a&b = a 说明第二位是0，因为每进位

 a&b = b 说明判断为是0，因为 0&b = b


(2) 取int型变量a的第k位 (k=0,1,2……sizeof(int))，即a> > k& 1 
因为我要取第k位，那么把第k位移到第0位，然后擦掉其他位


(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) 
因为限定是16的循环，那么左移很可能移出去，但是就像地球是圆的一样，从左边跑可以跑到，从右边跑也可以跑到，所以向左移多少就是向右移多少的补 （k+16-k = 16 就是跑了一圈），所以思想是当向左跑跑出界了的话，那么就把向右跑给插入进去吧。。。。

(6) int型变量a循环右移k次，即a=a> > k|a< < 16-k    (设sizeof(int)=16) 

定理1：设a，b为两个二进制数，则a+b = a^b + (a&b)<<1。
证明：a^b是不考虑进位时加法结果。当二进制位同时为1时，才有进位，因此 (a&b)<<1是进位产生的值，称为进位补偿。将两者相加便是完整加法结果。
定理2：使用定理1可以实现只用位运算进行加法运算。
证明：利用定理1中的等式不停对自身进行迭代。每迭代一次，进位补偿右边就多一位0，因此最多需要加数二进制位长度次迭代，进位补偿就变为0，这时运算结束。



(7)整数的平均值
对于两个整数x,y，如果用 (x+y)/2 求平均值，会产生溢出，因为 x+y 可能会大于INT_MAX，但是我们知道它们的平均值是肯定不会溢出的，我们用如下算法：
int average(int x, int y)    //返回X,Y 的平均值
{       
        return (x& y)+((x^y)> > 1); 
} 

x+y = x^y+(x&y)<<1;
x*2 = x<<1;
x/2 = x>>1;
所以(x+y)/2 = (x^y + x&y<<1)>>1 = x^y>>1 + x&y


512 * 7 = 512 * (4 + 2 + 1) = 512 * 4 + 512 * 2 + 512
= 512 << 2 + 512 << 1 + 51

512/7  因为不能约分，又不是2的倍数，所以除不尽，所以只能近似
512/8 = 512>>3 
 



(8)判断一个整数是不是2的幂,对于一个数 x > = 0，判断他是不是2的幂
boolean power2(int x)
{ 
      return ((x& (x-1))==0)& & (x!=0)；
} 
给定一个正整数（N <= 2^32），要求快速判断它是否为2的幂次方。（不可用循环） 
通常我们知道： 
       十进制         二进制 
2^0 == 1              0000 0001 
2^1 == 2              0000 0010 
2^2 == 4              0000 0100 
2^3 == 8              0000 1000 
2^4 == 16             0001 0000 
2^5 == 32             0010 0000 
从上述规律中我们可以得出，题目最终归结为判断此数的二进制表示（unsigned）中是否只有一位为1

因为是2进制，所以x-1会使得低位为1的位及其下面的位置全部错位，而其他高位位不变，这样，这样x&(x-1)将把他们共同的部分保留下来，也就是错位的地方被消除，从而可以消除一个1

x&x-1做一次运算将会消去最低位上的1
所以如果要计算一个数中二进制位1的个数可以这么做
int func(x)
{
    int countx = 0;
    while(x)
    {
        countx++;
        x = x&(x-1);
    }
    return countx;
}

(9) x 的 相反数 表示为 (~x+1) 还不如乘以-1



总结：a&0 ---清零特定位
      a&1 ---保留特定位
      a&b ---保留a和b都是1的位，也就是保留相加的进位
      a&(a-1)---除去最低位的0

评论

1 楼 gaoym1020 2011-01-02  

 (8)判断一个整数是不是2的幂,对于一个数 x > = 0，判断他是不是2的幂  
 boolean power2(int x)  
{   
       return ((x& (x-1))==0)& & (x!=0)；  
 }

是2的幂的整数具有以下特征：
a）二进制数中，只有一个位为1。如2：0000 0010，4：0000 0100，8：0000 1000
b）x为2的n次幂的数，x-1即为后n位为1的二进制数。如x=8：0000 1000，x-1=7：0000 0111
故，具有*x&(x-1)==0 && x!=0)的数，即为2的幂的数

(9) x 的 相反数 表示为 (~x+1) 还不如乘以-1 
在编程语言中，负数是以补码的方式表示的，也就是通过将与其对应的正数的二进制代码取反（即将1变成0，将0变成1），然后对其结果加1。
例如，-42就是通过将42的二进制代码的各个位取反，即对 00101010 取反得到11010101 ，然后再加1，得到11010110 ，即-42 。