二进制的运算

红太狼 2024-03-23 17:39 60阅读 0赞

#### 二进制的运算 ####

*  位与（&）
 *  位或（|）
 *  异或（^）
 *  取反
 *  常见位运算问题
 *   *  位操作实现乘除法
     *  位操作交换两数
     *  判断奇偶数
     *  求余数
     *  位操作交换符号
     *  位操作求绝对值
     *  位操作进行高低位交换
     *  位操作进行二进制逆序
     *  位操作统计二进制中 1 的个数
     *  检测整数 n 是否是 2 的幂次

## 位与（&） ##

类似于逻辑与运行，当条件都为true时，结果才为true。

> 0 & 0 = 0  
> 0 & 1 = 0  
> 1 & 0 = 0  
> 1 & 1 = 1

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

## 位或（|） ##

类似于逻辑或运行，当条件只要有一个为true时，结果就为true。

> 0 | 0 = 0  
> 0 | 1 = 1  
> 1 | 0 = 1  
> 1 | 1 = 1

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

## 异或（^） ##

异或运算，相同为0，不同为1。  
它在书本上的符号是这样的  ⨁ \\bigoplus ⨁。它也叫半加运算，就是数值相加之后不进位。比如二进制的1+1结果是10，进位为1再写0。如果不进位，那么1异或1就等于0。1与0的异或可以直接看作是相加。

> 0 ^ 0 = 0  
> 0 ^ 1 = 1  
> 1 ^ 0 = 1  
> 1 ^ 1 = 0

![bad7888211da45059ff70d5cf52d1b57.png][]

> 补充：相等的两个数值，异或的结果为0  
> 在对称加密算法中，经常会使用到异或运算。  
> 来个小案例，a=1314520, key=12345678。密文 b = a ^ key = 11038614。明文a = b ^ key = 1314520

## 取反 ##

~ 取反运算，0 则变为 1，1 则变为 0，如：

> ~1 0 0 1 1 = 0 1 1 0 0  
> ~1 0 1 0 1 = 0 1 0 1 0

## 常见位运算问题 ##

### 位操作实现乘除法 ###

数 x 向右移一位，相当于将 x 除以 2；数 x 向左移一位，相当于将 a 乘以 2

x <<= 3; // x = x << 3 , x = x*8
    x >>= 4; // x = x >> 4 , x = x/16
    x = (x<<1) + (x<<3); // x = x*2 + x*8 , x = x*10

### 位操作交换两数 ###

int x = 2, y = 5;
    //简写  x^=y, y^=x, x^=y; 
    
    x = x ^ y;
    y = y ^ x;
    x = x ^ y;

### 判断奇偶数 ###

将数转为二进制后，只要根据数的最后一位是 0 还是 1 就能判断奇偶。为 0 就是偶数，为 1 就是奇数。

// 判断是奇数，普通的
    public boolean isOdd1(int i) {
        
        return i % 2 != 0;
    }
    // 位与运算
    public boolean isOdd2(int i) {
        
        return 1 == (i & 1);
    }

### 求余数 ###

> 位与也是可以用来取余的，但是有一个条件：除数必须是2的n次幂才行。

27%8=3 （11011是27的二进制表示，1000是8的二进制表示，11是3的二进制表示）  
11011 & （1000 - 1）  
=11011 & 0111  
=00011

其实很明显了，在二进制计算中，  
一个数右移1位相当于除以2的商，而恰巧被移除出去的那一位就是除以2得到的余数。而且，不仅是除以2，对于一个数k要除以2的n次方，也就是相当于把k向右移n位，被移出去的n位即正好是我们要求是余数。那么问题就简单了，实际上，对于除数是2的n次方的算式，我们只需要得到被除数的低n位就可以了。而正好，对于2的n次方这样的数，我们将其转换为二进制之后，它就是第n+1位为1，其余低位都为0的数，因此我们将其减1，就得到了第n+1位为0，而其他位都为1的数。用此数与被除数k进行位与运算，就得到了被除数的低n位二进制数，也就是 k%n^2 的结果。

例如：27二进制是 11011  
27除以2的余数是，27二进制的低1位，余数是1。27除以2^3的余数是，27二进制的低3位，余数是011。  
27除以2=7余1 11011左移1位，商就是111，余数是1  
27除以8=3余3 11011左移3位，商就是11， 余数是011

> 总结：  
> 若一个数m满足：m=2^n，那么k % m = k & (m-1)

### 位操作交换符号 ###

交换符号将正数变成负数，负数变成正数  
整数取反加1，正好变成其对应的负数(补码表示)；负数取反加一，则变为其原码，即正数

int reversal(int a) {
        
      return ~a + 1;
    }

### 位操作求绝对值 ###

整数的绝对值是其本身，负数的绝对值正好可以对其进行取反加一求得，即我们首先判断其符号位  
（整数右移 31 位得到 0，负数右移 31 位得到 -1,即1…111…1(一共32个1)），然后根据符号进行相应的操作

int abs(int a) {
        
      int i = a >> 31;
      return i == 0 ? a : (~a + 1);
    }

上面的操作可以进行优化，可以将 i == 0 的条件判断语句去掉。我们都知道符号位 i 只有两种情况，即 i = 0 为正，i = -1 为负。对于任何数与 0 异或都会保持不变，与 -1 即 1…111…1(一共32个1) 进行异或就相当于对此数进行取反,因此可以将上面三目元算符转换为((a^i)-i)，即整数时 a 与 0 异或得到本身，再减去 0，负数时与 1…111…1(一共32个1) 异或将 a 进行取反，然后在加上 1，即减去 i(i =-1)

int abs2(int a) {
        
      int i = a >> 31;
      return ((a^i) - i);
    }

### 位操作进行高低位交换 ###

给定一个 16 位的无符号整数，将其高 8 位与低 8 位进行交换，求出交换后的值。

> 如：34520的二进制表示：10000110 11011000  
> 将其高8位与低8位进行交换，得到一个新的二进制数：11011000 10000110  
> 其十进制为55430

从上面移位操作我们可以知道，只要将无符号数 a>>8 即可得到其高 8 位移到低 8 位，高位补 0；将 a<<8 即可将 低 8 位移到高 8 位，低 8 位补 0，然后将 a>>8 和 a<<8 进行或操作既可求得交换后的结果。

unsigned short a = 34520;
    a = (a >> 8) | (a << 8);

### 位操作进行二进制逆序 ###

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

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

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

第一步:以每 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);

### 位操作统计二进制中 1 的个数 ###

统计二进制1的个数可以分别获取每个二进制位数，然后再统计其1的个数，此方法效率比较低。这里介绍另外一种高效的方法，同样以 34520 为例，我们计算其 a &= (a-1)的结果：  
第一次：计算前：1000 0110 1101 1000 计算后：1000 0110 1101 0000  
第二次：计算前：1000 0110 1101 0000 计算后：1000 0110 1100 0000  
第三次：计算前：1000 0110 1100 0000 计算后：1000 0110 1000 0000

我们发现，每计算一次，二进制中就少了一个 1。则我们可以通过下面方法去统计

count = 0  
    while(a){
          
    	a = a & (a - 1);  
    	count++;  
    }

> 补充，当一个数最后的统计结果为1时，说明此数是2的n次幂

### 检测整数 n 是否是 2 的幂次 ###

N如果是2的幂次，则N满足两个条件。

*  N > 0
 *  N的二进制表示中,只有一个1

因为N的二进制表示中只有一个1，所以使用N & (N - 1)将N唯一的一个1消去，应该返回0

public boolean isSecondPower(int x){
        
        return x>0 && 0 == (x & (x-1));
    }

[5662873f99eb413781283310ecfd3e17.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/cde7a16cda9f47a88b370853c7a4efc7.png
[f01012a2ece64836a498c42da1001ddb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/5b824e1864054cc2a3e5c51feaa7a9ce.png
[bad7888211da45059ff70d5cf52d1b57.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/8c9f6a1b53874c87befc2737dddcebb9.png