位运算的巧妙使用

叁歲伎倆 2022-11-28 10:36 135阅读 0赞

基本的位操作符有与、或、异或、取反、左移、右移这6种:

![在此输入图片描述][format_png]

位运算示例操作

<table> 
 <thead> 
  <tr> 
   <th>位运算</th> 
   <th>功能</th> 
   <th>示例</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>x &gt;&gt; 1</td> 
   <td>去掉最后一位</td> 
   <td>101101-&gt;10110</td> 
  </tr> 
  <tr> 
   <td>x &lt;&lt; 1</td> 
   <td>在最后加一个0</td> 
   <td>101101-&gt;1011010</td> 
  </tr> 
  <tr> 
   <td>x &lt;&lt; 1 | 1</td> 
   <td>在最后加一个1</td> 
   <td>101101-&gt;1011011</td> 
  </tr> 
  <tr> 
   <td>x | 1</td> 
   <td>把最后一位变成1</td> 
   <td>101100-&gt;101101</td> 
  </tr> 
  <tr> 
   <td>x &amp; -2</td> 
   <td>把最后一位变成0</td> 
   <td>101101-&gt;101100</td> 
  </tr> 
  <tr> 
   <td>x ^ 1</td> 
   <td>最后一位取反</td> 
   <td>101101-&gt;101100</td> 
  </tr> 
  <tr> 
   <td>x | (1 &lt;&lt; (k-1))</td> 
   <td>把右数第k位变成1</td> 
   <td>101001-&gt;101101,k=3</td> 
  </tr> 
  <tr> 
   <td>x &amp; ~ (1 &lt;&lt; (k-1))</td> 
   <td>把右数第k位变成0</td> 
   <td>101101-&gt;101001,k=3</td> 
  </tr> 
  <tr> 
   <td>x ^(1 &lt;&lt;(k-1))</td> 
   <td>右数第k位取反</td> 
   <td>101001-&gt;101101,k=3</td> 
  </tr> 
  <tr> 
   <td>x &amp; 7</td> 
   <td>取末三位</td> 
   <td>1101101-&gt;101</td> 
  </tr> 
  <tr> 
   <td>x &amp; (1 &lt;&lt; k-1)</td> 
   <td>取末k位</td> 
   <td>1101101-&gt;1101,k=5</td> 
  </tr> 
  <tr> 
   <td>x &gt;&gt; (k-1) &amp; 1</td> 
   <td>取右数第k位</td> 
   <td>1101101-&gt;1,k=4</td> 
  </tr> 
  <tr> 
   <td>x | ((1 &lt;&lt; k)-1)</td> 
   <td>把末k位变成1</td> 
   <td>101001-&gt;101111,k=4</td> 
  </tr> 
  <tr> 
   <td>x ^ (1 &lt;&lt; k-1)</td> 
   <td>末k位取反</td> 
   <td>101001-&gt;100110,k=4</td> 
  </tr> 
  <tr> 
   <td>x &amp; (x+1)</td> 
   <td>把右边连续的1变成0</td> 
   <td>100101111-&gt;100100000</td> 
  </tr> 
  <tr> 
   <td>x | (x+1)</td> 
   <td>把右起第一个0变成1</td> 
   <td>100101111-&gt;100111111</td> 
  </tr> 
  <tr> 
   <td>x | (x-1)</td> 
   <td>把右边连续的0变成1</td> 
   <td>11011000-&gt;11011111</td> 
  </tr> 
  <tr> 
   <td>(x ^ (x+1)) &gt;&gt; 1</td> 
   <td>取右边连续的1</td> 
   <td>100101111-&gt;1111</td> 
  </tr> 
  <tr> 
   <td>x &amp; -x</td> 
   <td>去掉右起第一个1的左边</td> 
   <td>100101000-&gt;1000</td> 
  </tr> 
  <tr> 
   <td>x&amp;0x7F</td> 
   <td>取末7位</td> 
   <td>100101000-&gt;101000</td> 
  </tr> 
  <tr> 
   <td>x&amp; ~0x7F</td> 
   <td>是否小于127</td> 
   <td>001111111 &amp; ~0x7F-&gt;0</td> 
  </tr> 
  <tr> 
   <td>x &amp; 1</td> 
   <td>判断奇偶</td> 
   <td>00000111&amp;1-&gt;1</td> 
  </tr> 
 </tbody> 
</table>

使用位运算的两点注意事项：

> 1.  位操作只能用于整形数据，对float和double类型进行位操作会被编译器报错。
> 2.  位操作符的运算优先级比较低，因为尽量使用括号来确保运算顺序

### 1. 判断一个数值是不是2的整数次方 ###

解题思路：

2的整数次方对应的二进制的最高位上只有一个1，如：8，二进制为 1000； 4，二进制为 0100，

那么将该数字减去1再与该数字进行与运算，减去1 后得到二进制：7，二进制为 0111；3，二进制为 0011，可以看出 8&7 为0，

4&3 为0

所以，如果 n 是2的整数次方，那么 n & ( n - 1 )结果一定为0:

n 的数值要大于 0

public class Main {
        
        public static void main(String[] args) {
            int n = 8;
            if ((n & (n-1)) == 0){
                System.out.println("整数的二次方 true");
            }else{
                System.out.println("不是整数的二次方");
            }
        }
    }

### 2. 使用位运算交换两个数字【不使用中间变量】 ###

**使用异或**

public class Main {
        
        public static void main(String[] args) {
            int n = 8, m = 10;
            n ^= m;
            m ^= n;
            n ^= m;
            System.out.println(n + ", " + m);
        }
    }

如： a = 13, b = 6:  
a的二进制为 13 = 8 + 4 + 1 = 1101(二进制)  
b的二进制为 6 = 4 + 2 = 110(二进制)

1.  a ^= b a = 1101 ^ 110 = 1011;
2.  b ^= a b = 110 ^ 1011 = 1101; 即b == 13
3.  a ^= b a = 1011 ^ 1101 = 110; 即a == 6

其他方法，**使用加减法**

public class Main {
        
        public static void main(String[] args) {
            int n = 8, m = 10;
            n = n + m;
            m = n - m;
            n = n - m;
            System.out.println(n + ", " + m);
        }
    }

### 3. 计算在一个 32 位的整数的二进制表示中有多少个 1 ###

循环使用x & (x-1)消去最后一位1，计算总共消去了多少次即可。

如：

13： 1101

12： 1100

相与：1100， 消去最后一位

public class Main {
        
        public static void main(String[] args) {
            // 计算在一个 32 位的整数的二进制表示中有多少个 1
            int m = 13, num = 0;
            while (true){
                if (m == 0) break;
                m &= (m-1);
                num ++;
            }
            System.out.println(num);
        }
        
    }

### 4. 正数变成负数，或者负数变成正数 ###

**变换符号只需要取反后加1即可**

public class Main {
        
        public static void main(String[] args) {
            // 计算在一个 32 位的整数的二进制表示中有多少个 1
            int m = -13;
            int changeM = ~m + 1;
            System.out.println(changeM);
        }
        
    }

### 5. 判断一个数值的奇偶 ###

只要根据最未位是0还是1来决定，为0就是偶数，为1就是奇数，所以只需要与 1 相与。

因此可以用if ((a & 1) == 0)代替if (a % 2 == 0)来判断a是不是偶数。

public class Main {
        
        public static void main(String[] args) {
            int m = -14;
            
            if ((m & 1) == 1){
                System.out.println("ji");
            }else{
                System.out.println("ou");
            }
        }
        
    }

### 6. 乘以2 的m次方操作 ###

乘以2的操作，即2的1次方，左移 1 位

System.out.println(10<<1);

推导扩展：

乘以2的m次方

System.out.println(10<<2); // 乘以 2的2次方，相当于乘以 4

### 7.除以2运算(负奇数的运算不可用) ###

System.out.println(10>>1);

### 8. 转换成绝对值 ###

public class Main {
        
        public static void main(String[] args) {
            int n = 12;
            
            System.out.println(0 >> 31); // 0
            System.out.println(10 >> 31);  // 0
            System.out.println(-10 >> 31);  // -1
            
            System.out.println((n ^ (n >> 31)) - (n >> 31));  // 12 
            
        }
        
    }

1. 首先：n>>31 取得n的符号

若n为正数，n>>31等于0；若n为负数，n>>31等于-1 若n为正数 n^0-0数不变；

2. 若 n 为负数 n^-1 需要计算 n 和 -1 的补码，异或后再取补码， 结果n变号并且绝对值减1，再减去-1就是绝对值

### 9.判断两数符号是否相同 ###

true 表示 x和y有相同的符号， false表示x，y有相反的符号。

System.out.println((a ^ b) > 0);

### 10. 求两个整数（int）的平均数 ###

System.out.println((a+b) >> 1);

### 11. 求两个整数的最大值 ###

int max(int a,int b){
    	return b & ((a-b) >> 31) | a & (~(a-b) >> 31);
    	/*如果a>=b,(a-b)>>31为0，否则为-1*/
    }

### 12.求两个整数的最小值 ###

int min(int a,int b){
    	return a & ((a-b) >> 31) | b & (~(a-b) >> 31);
    	/*如果a>=b,(a-b)>>31为0，否则为-1*/
    }

### 13. **两个整数的加法运算** ###

使用 `^` 和 `&` 将两个整数相加

1.  两个数异或：相当于两个数相加，而不考虑进位；
2.  两个数相与，并左移一位：相当于求得进位；

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xyczEzNTMyODEwMDQ_size_16_color_FFFFFF_t_70]

![在这里插入图片描述][20190213172431556.png]

13+11 = ？;

13 的二进制 1 1 0 1 -----a 13

11 的二进制 1 0 1 1 -----b 11

(a&b) <<1 -> 1 0 0 1 **0** \-----d 18

a^b -> 0 1 1 **0** \-----e 6

(d&e) <<1 -> 0 0 1 **0 0** \------f 4

d^e -> 1 0 1 **0 0** \-----g 20

(f&g) <<1 -> 0 1 **0 0 0** \------h 8

f^g -> 1 0 **0 0 0**  \------i 16

(h&i) <<1 -> 0 **0 0 0 0**  \------h 0 ---- -------- 没有进位了， 则退出循环

h^i -> 1 1 0 0 0 ------i 24

private static int getSum(int a, int b) {
        if (a == 0) return b;
        if (b == 0) return a;
        while (b != 0) {
            int carry = a & b; // 得到有进位的位置
            a = a ^ b; // 直接相加，但是没有进位
            b = carry << 1; // 得到进位
        }
        return a;
    }

--------------------

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1_size_16_color_FFFFFF_t_70][]

--------------------

[format_png]: /images/20221124/277d5b9b2a8d4522b7a2de2ab7eff712.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xyczEzNTMyODEwMDQ_size_16_color_FFFFFF_t_70]: /images/20221124/80b54a7f65164e88ad972093038a729f.png
[20190213172431556.png]: /images/20221124/d1962950576a4aa9a60c7ba47f55d8ee.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1_size_16_color_FFFFFF_t_70]: /images/20221124/1f157dcc92dd45dbb4e9cc1612a90089.png