百度360必应搜狗淘宝本站头条
当前位置:网站首页 > 文章教程 > 正文

位运算介绍与经典面试题总结(超全)

xsobi 2024-11-23 10:49 1 浏览


前言

位运算隐藏在编程语言的角落中,其神秘而又强大,暗藏内力,有些人光听位运算的大名的心中忐忑,还有些人更是一看到位运算就远远离去,我之前也是。但狡猾的面试官往往喜欢搞偷袭,抓住我们的弱点搞我们,为了防患于未然,特记此篇!

本篇的内容为位运算的介绍和一些比较经典的位运算问题进行介绍分析,当然,位运算这么牛,后面肯定还是要归纳总结的。

认识位运算

什么是位运算?

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

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

常见的运算符有与(&)、或(|)、异或(^)、取反(~)、左移(<<)、右移(>>是带符号右移 >>>无符号右移动)。下面来细看看每一种位运算的规则。

位运算 & (与)

规则:二进制对应位两两进行逻辑AND运算(只有对应位的值都是 1 时结果才为 1, 否则即为 0)即 0&0=0,0&1=0,1&1=1

例如:2 & -2


位运算 | (或)

规则:二进制对应位两两进行逻辑或运算(对应位中有一 个为1则为1) 即0|0=0,0|1=1,1|1=1

例如:2 | -2


位运算 ^ (异或)

规则:二进制对应位两两进行逻辑XOR (异或) 的运算(当对应位的值不同时为 1, 否则为 0)即0^0=0, 0^1=1, 1^1=0

例如:2 ^ -2


按位取反~

规则:二进制的0变成1,1变成0。


移位运算符

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

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

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

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

下面这张图可以很好地帮助你理解负数的移位运算符:


到这里,我想你应该对位运算有了初步的认识,在这里把上面提到的部分案例执行对比一下让你看一下可能会理解的更清晰:


位运算小技巧

在这里有些常用的位运算小技巧。

判断奇偶数

正常判断奇数偶数的时候我们会这样写:

if( n % 2 == 1)
    // n 是个奇数
}

使用位运算可以这么写:

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

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

交换两个数

对于传统的交换两个数,我们需要使用一个变量来辅助完成操作,可能会是这样:

int team = a;
a = b;
b = team;

但是使用位运算可以不需要借助额外空间完成数值交换:

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=0

原理已经写在注释里面了,是不是感觉非常diao呢?

二进制枚举

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


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

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位是否存在
    {
      //操作或者输出
    }
  }
}

位运算经典问题

有了上面的位运算基础,我们怎么用位运算处理实际问题呢?或者有哪些经典的问题可以用位运算来解决呢。

不用加减乘除做加法

题目描述

写一个函数,求两个整数之和,要求在函数体内不得使用+、-、*、/四则运算符号。

分析: 这道题咋一听可能没啥思路,简单研究一下位运算还是能独立推出来和理解的。

当然,解决这题前,需要了解上面的四种位运算。还要知道二进制的运算:0+0=0,0+1=1,1+1=0(进位)

对于加法的一个二进制运算。如果不进位那么就是非常容易的。这时候相同位都为0则为0,0和1则为1.满足这种运算的异或(不相同取1,相同取0)和或(有一个1则为1)都能满足.

但事实肯定有进位的运算啊!看到上面操作的不足之后,我们肯定还需要解决进位的问题对于进位的两数相加,这种核心思想为

  • 用两个数,一个正常m相加(不考虑进位的)。用异或a^b就是满足这种要求,先不考虑进位(如果没进位那么就是最终结果)。另一个专门考虑进位的n。两个1需要进位。所以我们用a&b与记录需要进位的。但是还有个问题,进位的要往上面进位,所以就变成这个需要进位的数左移一位。
  • 然后就变成m+n重新迭代开始上面直到不需要进位的(即n=0时候)。


实现代码为:

public class Solution {
     public int Add(int num1,int num2) {
  /*
   *  5+3   5^3(0110)   5&3(0001) 
   *  0101    
   *  0011 
   */
  int a=num1^num2;
  int b=num1&num2;
  b=b<<1;
  if(b==0)return a;
  else {
   return Add(a, b);
  }        
  }
}

当然,这里也可以科普一下二进制求加法:average = (a&b) + ((a^b)>>1) ;

二进制中1的个数

这是一道经典题,在剑指offer上也有对应题目,其具体题目要求输入一个整数,输出该数二进制表示中1的个数(其中负数用补码表示)

对于这个问题,不用位运算将它转成二进制字符串直接枚举字符'1'的个数也可以直接求出来,但是这样做是没有灵魂的并且效率比较差。这里提供两种解决思路

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

首先要知道:

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为1。所以我们用2的正数次幂与知道的数分别进行与运算操作。如果结果不为0,那么就说明这位为1.(前面31个都是大于0的最后一个与结果是负数但是如果该位为1那么结果肯定不为0)


具体代码实现为:

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停止计算次数就好了,如下图共进行三次运算那么n的二进制中就有三个1。

实现代码为:

public class Solution {
    public int NumberOf1(int n) {
    int count=0;
    while (n!=0) {
     n=n&(n-1);
     count++;
    }
    return count;
 }
}

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

问题描述:

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

说明:你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

分析:

这是一道简单的面试题,面试官常问怎么样用不太复杂的方法找出数组中仅出现一次的数字(其他均出现两次),暴力枚举或者使用其他的存储结构都不够优化,而这个问题最高效的答案就是使用位运算。首先你要注意两点:

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

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


class Solution {
    public int singleNumber(int[] nums) {
        int value=0;
        for(int i=0;i<nums.length;i++)
        {
            value^=nums[i];
        }
        return value;
    }
}

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

问题描述:

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次。找出那个只出现了一次的元素。

说明:你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

分析:

这题和上一题的思路略有不同,这题其他数字出现了3次,那么我们如果直接使用位运算异或操作的话无法直接找到结果,就需要巧妙的运用二进制的其他特性:判断整除求余操作。即判断所有数字二进制1的总个数和0的总个数一定有一个不是三的整数倍,如果0不是三的整数倍那么就说明结果的该位二进制数字为0,同理否则为1.


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

具体代码为:

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)
                value+=(1<<i);
        }
        return value;
    }
}

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

题目描述

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

思路

上面的问题处理和理解起来可能比较容易,但是这个问题可能稍微复杂一点,但是这题可以通过特殊的手段转化为上面只出现一次的一个数字问题来解决,当然核心的位运算也是异或^

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

具体可以参考下图流程:


实现代码为:

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;
}

private int getFirst1(int val) {
    int index=0;
    while (((val&1)==0&&index<32))
    {
        val>>=1;// val=val/2
        index++;
    }
    return index;
}

结语

当然,上面的问题可能有更好的解法,也有更多经典位运算问题将在后面归纳总结,希望本篇的位运算介绍能够让你有所收获,对位运算能有更深一点的认识。对于很多问题例如博弈问题等二进制位运算能够很巧妙的解决问题,日后也会分享相关内容,敬请期待!

原创不易,如果觉得有所收获,希望大家点赞、分享、转发一键三连帮忙扩散,谢谢!

我的公众号:bigsai 我的头条号:程序员bigsai

咱们下次再见!

相关推荐

js向对象中添加元素(对象,数组) js对象里面添加元素

一、添加一个元素对象名["属性名"]=值(值:可以是一个值,可以是一个对象,也可以是一个数组)这样添加进去的元素,就是一个值或对象或数组...

JS小技巧,如何去重对象数组?(一)

大家好,关于数组对象去重的业务场景,想必大家都遇到过类似的需求吧,这对这样的需求你是怎么做的呢。下面我就先和大家分享下如果是基于对象的1个属性是怎么去重实现的。方法一:使用.filter()和....

「C/C++」之数组、vector对象和array对象的比较

数组学习过C语言的,对数组应该都不会陌生,于是这里就不再对数组进行展开介绍。模板类vector模板类vector类似于string,也是一种动态数组。能够在运行阶段设置vector对象的长度,可以在末...

如何用sessionStorage保存对象和数组

背景:在工作中,我将[{},{}]对象数组形式,存储到sessionStorage,然后ta变成了我看不懂的形式,然后我想取之用之,发现不可能了~记录这次深刻的教训。$clickCouponIndex...

JavaScript Array 对象 javascript的array对象

Array对象Array对象用于在变量中存储多个值:varcars=["Saab","Volvo","BMW"];第一个数组元素的索引值为0,第二个索引值为1,以此类推。更多有...

JavaScript中的数组Array(对象) js array数组

1:数组Array:-数组也是一个对象-数组也是用来存储数据的-和object不同,数组中可以存储一组有序的数据,-数组中存储的数据我们称其为元素(element)-数组中的每一个元素都有一...

数组和对象方法&amp;数组去重 数组去重的5种方法前端

列举一下JavaScript数组和对象有哪些原生方法?数组:arr.concat(arr1,arr2,arrn);--合并两个或多个数组。此方法不会修改原有数组,而是返回一个新数组...

C++ 类如何定义对象数组?初始化数组?linux C++第43讲

对象数组学过C语言的读者对数组的概念应该很熟悉了。数组的元素可以是int类型的变量,例如int...

ElasticSearch第六篇:复合数据类型-数组,对象

在ElasticSearch中,使用JSON结构来存储数据,一个Key/Value对是JSON的一个字段,而Value可以是基础数据类型,也可以是数组,文档(也叫对象),或文档数组,因此,每个JSON...

第58条:区分数组对象和类数组对象

示例设想有两个不同类的API。第一个是位向量:有序的位集合varbits=newBitVector;bits.enable(4);bits.enable([1,3,8,17]);b...

八皇后问题解法(Common Lisp实现)

如何才能在一张国际象棋的棋盘上摆上八个皇后而不致使她们互相威胁呢?这个著名的问题可以方便地通过一种树搜索方法来解决。首先,我们需要写一个函数来判断棋盘上的两个皇后是否互相威协。在国际象棋中,皇后可以沿...

visual lisp修改颜色的模板函数 怎么更改visual studio的配色

(defunBF-yansemokuai(tuyuanyanse/ss)...

用中望CAD加载LISP程序技巧 中望cad2015怎么加载燕秀

1、首先请加载lisp程序,加载方法如下:在菜单栏选择工具——加载应用程序——添加,选择lisp程序然后加载,然后选择添加到启动组。2、然后是添加自定义栏以及图标,方法如下(以...

图的深度优先搜索和广度优先搜索(Common Lisp实现)

为了便于描述,本文中的图指的是下图所示的无向图。搜索指:搜索从S到F的一条路径。若存在,则以表的形式返回路径;若不存在,则返回nil。...

两个有助于理解Common Lisp宏的例子

在Lisp中,函数和数据具有相同的形式。这是Lisp语言的一个重大特色。一个Lisp函数可以分析另一个Lisp函数;甚至可以和另一个Lisp函数组成一个整体,并加以利用。Lisp的宏,是实现上述特色的...