清风新雨

位运算符总结

发表于 更新于 分类于
本文字数： 2.2k 阅读时长 ≈ 8 分钟

​ 本篇主要详细介绍一下所有位运算符号以及常见的用法

🎯位运算总结

参考文章：超全的位运算介绍与总结 - 知乎

⚓什么是位运算？

什么是位运算？

程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算就是直接对整数在内存中的二进制位进行操作。

位运算就是直接操作二进制数，那么有哪些种类的位运算呢？

常见的位运算有与（&），或（|），异或（^），取反（~），左移（<<）,右移（>>）

下面来详细介绍一下

位运算与（&）

规则：只有对应位的值都是 1 时结果才为 1, 否则即为 0

​ 0 0 0 0 0 1 0

​ 1 1 1 1 1 1 0

结果：0 0 0 0 0 1 0

位运算或（|）

规则：对应位中有一 个为1则为1

​ 0 0 0 0 0 1 0

​ 1 1 1 1 1 1 0

结果：1 1 1 1 1 1 0

位运算异或（^）

规则：当对应位的值不同时为 1, 否则为 0

​ 0 0 0 0 0 1 0

​ 1 1 1 1 1 1 0

结果：1 1 1 1 1 0 0

按位取反（~）

规则：二进制的0变成1，1变成0

移位运算符

左移右移判断方法：箭头所☞的方向

左移运算<<：左移后右边位补 0

右移运算>>：右移后左边位补原最左位值(可能是0，可能是1)

右移运算>>>：右移后左边位补 0

对于左移运算符<<没有悬念右侧填个零无论正负数相当于整个数乘以2

而右移运算符就有分歧了，分别是左侧补0>>>和左侧补原始位>>，如果是正数没争议左侧都是补0，达到除以2的效果；如果是负数的话左侧补0>>>那么数值的正负会发生改变，会从一个负数变成一个相对较大的正数。而如果是左侧补原始位(负数补1)>>那么整个数还是负数，也就是相当于除以2的效果。

负数表示：

补码 ：

1
2
3
4
5
6
// 正数不变，负数：正数取反后加1
+5 = 00000101
-5 = 11111011  // (00000101取反得11111010，再加1)

// 优点：只有一个0
0 = 00000000

补码负数进行右移运算时，采用算术右移规则：

  • 左侧空出的位用符号位（1）填充
  • 结果保持负数性质
1
2
原始：11111000 (-8)
右移：11111100 (-4)  ← 左侧补1

🔎位运算在算法中的实用技巧

判断奇偶数

1
2
3
if(n & 1 == 1){
    // n 是个奇数。
}

其核心就是判断二进制的最后一位是否为1，如果为1那么结果加上2^0=1一定是个奇数，否则就是个偶数。

交换两个数

对于传统的交换两个数，我们需要使用一个变量来辅助完成操作，但是使用位运算可以不需要借助额外空间完成数值交换：

1
2
3
a=a^b;//a=a^b
b=a^b;//b=(a^b)^b=a^0=a
a=a^b;//a=(a^b)^(a^b^b)=0^b=b

二进制枚举

在遇到子集问题的处理时候，我们有时候会借助二进制枚举来遍历各种状态(效率大于dfs回溯)。这种就属于排列组合的问题了，对于每个物品(位置)来说，就是使用和不使用的两个状态，而在二进制中刚好可以用1和0来表示。而在实现上，通过枚举数字范围分析每个二进制数字各符号位上的特征进行计算求解操作即可。

二进制枚举的代码实现为：

1
2
3
4
5
6
7
8
9
10
for(int i = 0; i < (1<<n); i++) //从0～2^n-1个状态
{
  for(int j = 0; j < n; j++) //遍历二进制的每一位 共n位
  {
    if(i & (1 << j))//判断二进制数字i的第j位是否存在
    {
      //操作或者输出
    }
  }
}

🚀位运算经典问题

二进制中1的个数

其具体题目要求输入一个整数，输出该数二进制表示中1的个数(其中负数用补码表示)

法一： 大家知道每个类型的数据它的背后实际都是二进制操作。大家知道int的数据类型的范围是(-231,231 -1)。并且int有32位。但是并非32位全部用来表示数据。真正用来表示数据大小的也是31位。最高位用来表示正负。

首先要知道：

1
2
3
4
5
6
7
1<<0=1 =00000000000000000000000000000001
1<<1=2 =00000000000000000000000000000010
1<<2=4 =00000000000000000000000000000100
1<<3=8 =00000000000000000000000000001000
. . . . . .
1<<30=2^30 =01000000000000000000000000000000
1<<31=-2^31 =10000000000000000000000000000000

具体代码实现为：

1
2
3
4
5
6
7
8
9
10
11
public int NumberOf1(int n) {
  int va=0;
  for(int i=0;i<32;i++)
  {
    if((n&(1<<i))!=0)
    {                    
      va++;
    }
  }
  return va;          
}

法二是运用n&(n-1)。n如果不为0，那么n-1就是二进制第一个为1的变为0，后面全为1.这样的n&(n-1)一次运算就相当于把最后一个1变成0.这样一直到运算的数为0停止计算次数就好了。

实现代码为：

1
2
3
4
5
6
7
8
9
10
public class Solution {
    public int NumberOf1(int n) {
       int count=0;
       while (n!=0) {
           n=n&(n-1);
           count++;
       }
       return count;
    }
}

只出现一次的(一个)数字①

问题描述：

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

  • 0和任意数字进行异或操作结果为数字本身.
  • 两个相同的数字进行异或的结果为0.

具体的操作就是用0开始和数组中每个数进行异或，得到的值和下个数进行异或，最终获得的值就是出现一次(奇数次)的值。

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int singleNumber(int[] nums) {
        int value=0;
        for(int i=0;i<nums.length;i++)
        {
            value^=nums[i];
        }
        return value;
    }
}

只出现一次的(一个)数字②

问题描述：

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

在具体的操作实现上，问题中给出数组中的数据在int范围之内，那么我们就可以在实现上可以对int的32个位每个位进行依次判断该位1的个数求余3后是否为1，如果为1说明结果该位二进制为1可以将结果加上去。最终得到的值即为答案。

具体代码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int singleNumber(int[] nums) {
        int value=0;
        for(int i=0;i<32;i++)
        {
            int sum=0;
            for(int num:nums)
            {
                if(((num>>i)&1)==1)
                {
                    sum++;
                }
            }
            if(sum%3==1)       //只有那个单独的数会多出一个1
                value+=(1<<i);
        }
        return value;
    }
}

只出现一次的(两个)数字③

题目描述

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

具体思路就是想办法将数组逻辑上一分为二！先异或一遍到最后得到一个数，得到的肯定是a^b(假设两个数值分别为a和b)的值。在看异或^的属性：不同为1，相同为0. 也就是说最终这个结果的二进制为1的位置上a和b是不相同的。而我们可以找到这个第一个不同的位，然后将数组中的数分成两份，该位为0的进行异或求解得到其中一个结果a，该位为1的进行异或求解得到另一个结果b。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
private int getFirst1(int val) {
    int index=0;
    while (((val&1)==0&&index<32))
    {
        val>>=1;// val=val/2
        index++;
    }
    return index;
}
public int[] singleNumbers(int[] nums) {
    int value[]=new int[2];
    if(nums.length==2)
        return  nums;
    int val=0;//异或求的值
    for(int i=0;i<nums.length;i++)
    {
        val^=nums[i];
    }
    int index=getFirst1(val);
    int num1=0,num2=0;
    for(int i=0;i<nums.length;i++)
    {
        //这里其实是把两个数分别放到两个组进行异或计算
        if(((nums[i]>>index)&1)==0)//如果这个数第index为0 和num1异或
            num1^=nums[i];
        else//否则和 num2 异或
            num2^=nums[i];
    }
    value[0]=num1;
    value[1]=num2;
    return  value;
}

结语

到这里一些位运算的基本知识点就总结完毕了，当然鼠鼠也会不定期更新一些题目进来

-------------本文结束感谢您的阅读-------------