一起学算法（位运算篇）

待我称王封你为后i 2023-10-14 10:32 24阅读 0赞

### 1.位运算 ###

#### 1.二进制数值表示 ####

在计算机中，我们可以用单纯的0和1来表示数字，一般不产生歧义，我们会在数字的右下角写上它的进制，例如：1010（10）其表示的是1010，1010（2）表示的是10

#### 2.二进制加法 ####

> 二进制加法采用的是从低到高的位次相加，当相加的和为2时，则向高位进位

例如：

![8b838455a5442427852dace90849bad3.png][]

#### 3.二进制的减法 ####

> 二进制减法采用从低到高的位次依次相减，当遇到0减1的情况，则向高位借位

例如：

![97bfd4012da48a32c5484a5d97fbc7d5.png][]

### 2.位运算简介 ###

![1dfad19cfeb95aa14b035923064fd2dd.png][]

### 3.位运算概括 ###

#### 1.布尔运算 ####

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td>运算符表示</td> 
   <td>含义</td> 
   <td>示例</td> 
  </tr> 
  <tr> 
   <td>&amp;</td> 
   <td>位与</td> 
   <td>x&amp;y</td> 
  </tr> 
  <tr> 
   <td>|</td> 
   <td>位或</td> 
   <td>x|y</td> 
  </tr> 
  <tr> 
   <td>^</td> 
   <td>异或</td> 
   <td>x^y</td> 
  </tr> 
  <tr> 
   <td>~</td> 
   <td>按位取反</td> 
   <td>x~y</td> 
  </tr> 
 </tbody> 
</table>

##### 1.位与（一假便假） #####

public static void main(String[] args) {
            int a=110;
            int b=0b110;
            System.out.println(a);//110
            System.out.println(b);//6
        }

*  以0b作为前缀的表示它是一个二进制数

###### **位与运算符的应用：** ######

###### **1.奇偶性判定** ######

一般我们判断奇偶数的时候，都是取模进行判断

int a=15;
            if(a%2==0){
                System.out.println("我是一个偶数");
            }else{
                System.out.println("我是一个奇数");
            }

###### 我们学了位运算之后就可以这样写 ######

int a=15;
            if((a&1)==0){
                System.out.println("我是一个偶数");
            }else{
                System.out.println("我是一个奇数");
            }

###### 这是因为在二进制中奇数的最后一位是1，偶数的最后一位是0，故&可以求得该数奇偶性 ######

###### **2.取末5位** ######

> **给定一个数，求它的二进制表示的末5位，以十进制输出即可**

**可以给 给定的数位与个0b11111,取到末5位的值**

x&0b11111

###### **3.消除末尾5位** ######

> **给定一个数32位的整数，要求消除它的末5位**

**（11111111111111111111111111100000）（2）**

**代码这么写确实是复杂，看到都有点头晕，一般我们把它转成16进制，每4个二进制可以转换为一个16进制的数，所以得到的16位进制的数为0xffffffe0**

x&0xffffffe0
    //f代表的是4个1  e代表的是3个1，1个0   0代表的是4个0

###### **4.消除末尾连续1** ######

> 给出一个整数，现要求将这个整数转换成二进制数，将末尾连续的1都变为0，输出改变后的数字

*  原二进制表示形式：

![2cb1f90b2eaad00b81ca8bbe453bca9c.png][]

*  如果我们给这个原二进制数字上末尾加个1：

![e85a75ee8ead7b0f55e297e6acef1458.png][]

*  然后将这两个数进行位与运算：

![77807c6c4960cb3284628a5081b158bd.png][]

###### **5.2的幂判定** ######

> **怎么样才能判断一个正数是不是2的幂次？**

*  **如果一个数是2的幂次，它的二进制表示必然是：**

![c0ff15551c988b645d4d5f2c7659f9d9.png][]

*  我们将它减1，即2的k次减1的二进制表示如下：

![45620b8bb2270c32b5e6c4b2c33993a0.png][]

*  于是这两个数位与的结果也为0，于是我们知道一个数x是2的幂次，那么x&(x-1)必然为0
 *      (x&(x-1))==0

##### 2.位或（一真便真） #####

###### 1.位或运算符的应用 ######

###### 1.设置标记位 ######

> 给定一个数，判断它二进制低位的第5位，如果是0，则将它置为1

x|0b10000

###### 2.置空标记位 ######

*  首先，强行将低位的第5位换成1
 *  然后，强行将低位的第5位去掉

int a=0b10000
    ((x|a)-a)

###### 注意：直接减是不行的，因为我们要保证那一位为1，不然会造成借位，影响结果 ######

###### 3.低位连续零变一 ######

> 给定一个整数x,将它低位连续的0都变为1

*  假设这个整数低位有连续k个零，二进制表示为：

![fe5513d1b0c431b11229e8f788cfb241.png][]

*  减一操作得：

![d9d6aeb8fd2dc9511c7716ef1502a3c6.png][]

*  两数进行位或操作：

![bfe6dd2d1d8f915437ec6e406434aacb.png][]

x|(x-1)

###### 4.低位首零变一 ######

##### 3.异或（相同为0，不同为1） #####

###### 1.异或运算符的应用 ######

###### 1.标记位取反 ######

> 给定一个数，将它的低位数起的第4位进行取反，0变1 1变0

x^0b10000

###### 2.变量交换 ######

> 给定两个数，用异或运算交换它们的值

int a=5;
         int b=15;
         a=a^b;
         b=a^b;
         a=a^b;
         System.out.println(a);//15
         System.out.println(b);//5

###### 3.出现奇数次的数 ######

> 输入n个数，其中只有一个数出现了奇数次，其他所有数都出现了偶数次，求这个出现了奇数次的数

根据异或的性质，两个一样的数异或结果为0，也就是所有出现偶数次的数异或为0，那么把n个数都异或一下，得到的数一定是那个出现奇数的数

int[] num={2,2,3,4,4,5,5};
             int ans=0;
             for(int n:num){
                 ans^=n;
             }
            System.out.println(ans);

###### 4.丢失的数 ######

如果两个相同的数异或为零，那么这个数中，处了丢失的数之外，其余的数都可以找到两两结对异或得零，最后的结果就是0和丢失的数异或，因为0和任何数异或都是这个数的本身，自然地到了丢失的数

###### 5.简单加密 ######

基于两个数异或为0，任何数和零异或为其本身这两个特点，异或还可以用来做简单的加密，将明文异或上一个固定的数变成密文后，可以通过继续异或上这个数，再将密文转成明文

##### 4.按位取反 #####

0变1 1变0

#### 2.移位位运算 ####

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td>运算符表示</td> 
   <td>含义</td> 
   <td>示例</td> 
  </tr> 
  <tr> 
   <td>&lt;&lt;</td> 
   <td>左移</td> 
   <td>x&lt;&lt;y</td> 
  </tr> 
  <tr> 
   <td>&gt;&gt;</td> 
   <td>右移</td> 
   <td>x&gt;&gt;y</td> 
  </tr> 
 </tbody> 
</table>

##### 1.左移： #####

其中x<<y代表将二进制的x的末尾添加y个0，向左移动了y位 1011<<3 =1011000

##### 2.右移： #####

其中x>>y代表将二进制的x的右边截掉y个0，向右移动了y位 101111>>3 =101

### 4.将一个hash表压缩成一个数字(只是适用于元素较少的hash表) ###

空集  -------0
    只含有第i个元素的集合{i}---------1<<i
    含有全部n个元素的集合{0，1，...，n-1}-------(1<<n)-1
    判断第i个元素是否属于集合S-------------if(S>>1&1)
    向集合S中加入第i个元素--------------S|1<<i;
    从集合S中取出第i个元素--------------S&~(1<<i)   S^(1<<i)
    集合S和T的并集------------S|T
    集合S和T的交集------------S&T

#### leetcode题单： ####

[位1的个数][1]

public int hammingWeight(int n) {
          int count=0;
         for(int i=0;i<32;i++){
               if((n&1)==1){
                  count++;
              }
              n>>=1;
         }
          return count;
        }

[只出现一次的数字][Link 1]

public int singleNumber(int[] nums) {
                    if(nums.length==0){
                return 0;
            }
            Arrays.sort(nums);
            Stack stack=new Stack();
            for (int i = 0; i<=nums.length-1; i++) {
                stack.push(nums[i]);
                if(stack.peek().equals(nums[nums.length-1])){
                    return (int)stack.peek();
                }
                if(stack.peek().equals(nums[i+1])){
                    stack.pop();
                    i++;
                }else{
                    return (int)stack.peek();
                }
    
    
            }
           return (int)stack.peek();
        }

[8b838455a5442427852dace90849bad3.png]: https://img-blog.csdnimg.cn/img_convert/8b838455a5442427852dace90849bad3.png
[97bfd4012da48a32c5484a5d97fbc7d5.png]: https://img-blog.csdnimg.cn/img_convert/97bfd4012da48a32c5484a5d97fbc7d5.png
[1dfad19cfeb95aa14b035923064fd2dd.png]: https://img-blog.csdnimg.cn/img_convert/1dfad19cfeb95aa14b035923064fd2dd.png
[2cb1f90b2eaad00b81ca8bbe453bca9c.png]: https://img-blog.csdnimg.cn/img_convert/2cb1f90b2eaad00b81ca8bbe453bca9c.png
[e85a75ee8ead7b0f55e297e6acef1458.png]: https://img-blog.csdnimg.cn/img_convert/e85a75ee8ead7b0f55e297e6acef1458.png
[77807c6c4960cb3284628a5081b158bd.png]: https://img-blog.csdnimg.cn/img_convert/77807c6c4960cb3284628a5081b158bd.png
[c0ff15551c988b645d4d5f2c7659f9d9.png]: https://img-blog.csdnimg.cn/img_convert/c0ff15551c988b645d4d5f2c7659f9d9.png
[45620b8bb2270c32b5e6c4b2c33993a0.png]: https://img-blog.csdnimg.cn/img_convert/45620b8bb2270c32b5e6c4b2c33993a0.png
[fe5513d1b0c431b11229e8f788cfb241.png]: https://img-blog.csdnimg.cn/img_convert/fe5513d1b0c431b11229e8f788cfb241.png
[d9d6aeb8fd2dc9511c7716ef1502a3c6.png]: https://img-blog.csdnimg.cn/img_convert/d9d6aeb8fd2dc9511c7716ef1502a3c6.png
[bfe6dd2d1d8f915437ec6e406434aacb.png]: https://img-blog.csdnimg.cn/img_convert/bfe6dd2d1d8f915437ec6e406434aacb.png
[1]: https://leetcode.cn/problems/number-of-1-bits/
[Link 1]: https://leetcode.cn/problems/single-number/