位运算（＜＜移位＞＞、与&、或|、反~、异或^）及运用【求子集】【判相等】...（各类问题持续更新）_如何用位运算判断两个数

概念不用多说，上图（懒得自己做，图源菜鸟教程）

位运算规律

位运算高级操作

 

目录

一、与&的性质及运用

1、与的性质

2、输出一个正数二进制表示中1的个数

         3、用一条语句判断一个整数是不是2的整数次方。

         4、取指定位数

5、判断奇偶

二、或|的性质及运用

1、或的性质

2、常用来对一个数据的某些位设置为1

三、异或^的性质及运用

1、异或的性质

2、用异或交换两个数的值不依赖临时变量

3、判断两个整数a，b是否相等

四、移位运算

1、移位的性质

2、两数的中位数

五、位运算综合运用

1、位运算求子集（通过计算二进制数的1的位置来计算子集

一、与&的性质及运用

1、与的性质

是满足交换律和结合律的

按位与（&）其功能是参与运算的两数各对应的二进制位相与。只有对应的两个二进制位均为1时，结果位才为1，否则为0 。参与运算的数以补码方式出现。

把一个整数减去1之后再和原来的整数做位与运算，得到的结果相当于是把整数的二进制表示中的最右边一个1变成0 。

2、输出一个正数二进制表示中1的个数

一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0 。 那么一个整数的二进制表示中有多少个1，就可以进行多少次这样的操作。

public int count(int a){
    int num = 0;
    while(a){
        a &= (a-1);
        num++;
    }
    return num;
}

3、用一条语句判断一个整数是不是2的整数次方。

一个整数如果是2的整数次方，那么它的二进制表示中有且只有一位是1，而其它所有位都是0 。 根据前面的分析，把这个整数减去1后再和它自己做与运算，这个整数中唯一的1就变成0了。

public boolean Is2(int a){
    if(a&(a-1) == 0) return true;
    else return false;
}

4、取指定位数

取一个数的指定位

比如取数 X=1010 1110 的低4位，只需要另找一个数Y，令Y的低4位为1，其余位为0，即Y=0000 1111，然后将X与Y进行按位与运算（X&Y=0000 1110）即可得到X的指定位。

5、判断奇偶

只要根据最未位是0还是1来决定，为0就是偶数，为1就是奇数。因此可以用if ((a & 1) == 0)代替if (a % 2 == 0)来判断a是不是偶数。

二、或|的性质及运用

1、或的性质

是满足交换律和结合律的

负数按补码形式参加按位或运算。

2、常用来对一个数据的某些位设置为1

比如将数 X=1010 1110 的低4位设置为1，只需要另找一个数Y，令Y的低4位为1，其余位为0，即Y=0000 1111，然后将X与Y进行按位或运算（X|Y=1010 1111）即可得到。

三、异或^的性质及运用

1、异或的性质

1、交换律

2、结合律 (a^b)^c == a^(b^c)

3、对于任何数x，都有 x^x=0，x^0=x

4、自反性: a^b^b=a^0=a;

2、用异或交换两个数的值不依赖临时变量

public void Swap(int  &a,  int  &b){  
  if  (a  !=  b){  
    a  ^=  b; //a=a^b
    b  ^=  a; //b=b^(a^b) = (b^b)^a = a 
    a  ^=  b; //a=(a^b)^a = (a^a)^b = b
        }  
}

3、判断两个整数a，b是否相等

　return （（a ^ b） == 0

四、移位运算

1、移位的性质

左移1位相当于该数乘以2，左移2位相当于该数乘以2*2＝4,15＜＜2=60，即乘了４。但此结论只适用于该 数左移时被溢出舍弃的高位中不包含1的情况。 
假设以一个字节（８位）存一个整数，若ａ为无符号整型变量，则ａ＝64时，左移一位时溢出的是0 ，而左移2位时，溢出的高位中包含1。 

右移1位相当于该数除2，运算符是用来将一个数的各二进制位右移若干位，移动的位数由右操作数指定（右操作数必须是非负 值），移到右端的低位被舍弃，对于无符号数，高位补0。对于有符号数，某些机器将对左边空出的部分 用符号位填补（即“算术移位”），而另一些机器则对左边空出的部分用0填补（即“逻辑移位”）。注 意：对无符号数,右移时左边高位移入0；对于有符号的值,如果原来符号位为0(该数为正),则左边也是移 入0。如果符号位原来为1(即负数),则左边移入0还是1,要取决于所用的计算机系统。有的系统移入0,有的 系统移入1。移入0的称为“逻辑移位”,即简单移位；移入1的称为“算术移位”。 例： a的值是八进制数113755： 
   a:1001011111101101 （用二进制形式表示）    a>>1: 0100101111110110 (逻辑右移时)    a>>1: 1100101111110110 (算术右移时) 
   在有些系统中,a>>1得八进制数045766,而在另一些系统上可能得到的是145766

注意：

n为非负数时，>> 1和/ 2的结果是一样的
n为负数且还是偶数时，>> 1和/ 2的结果是一样的
n为负数且还是奇数时，>> 1和/ 2的结果是不一样的
原因是奇数除二会发生截断现象。而>> 1和/ 2在n为负奇数时截断的反向不一样。

-5 / 2 = -(int)2.5 = -2，这里是把绝对值变小了，加个负号，结果就变大了。
-5 >> 1 = (1011) >> 1 = (1101) = -3，假设用4-bit表示一个整数，补码表示。发现结果变小了。
我们纵向比较一下

-5 / 2 = -2，5 / 2 = 2。这表明除二是向零取整
-5 >> 1 = -3，5 >> 1 = 2。这表明右移一位是向下取整
所以我们之前说除二向下取整的说法不明确，应该说成非负数除二是向下取整，整数除二是向零取整。

有了这个之后，我们就发现二分取中点的次完美写法是mid = (l + r) >> 1。详情见二分以及编程过程中求中点各种写法思想解析以及完美写法

2、两数的中位数

public void Test(int a,int b){
    //通过位运算不会造成溢出
	int mid = a + (a - b) >> 1;
}

五、位运算综合运用

1、位运算求子集（通过计算二进制数的1的位置来计算子集）