查看原文
其他

盘点:这 7 道位运算面试题,哪一题你能做对?

The following article is from 小浩算法 Author 程序员浩哥

点击关注上方“五分钟学算法”,

设为“置顶或星标”,第一时间送达干货。

转自小浩算法



以下是目录,列出的全部内容都应该进行掌握:


  • 位运算基础

  • 位运算的奇淫技巧

  • 两数之和

  • 二的幂

  • 一的个数

  • 只出现一次的数字Ⅰ

  • 只出现一次的数字Ⅱ



01PART位运算基础

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

首先我们还是简单列下常规的位运算:



基本常用常考的,也就这么多。相信大家都知道,也就没什么好说的。



02PART位运算的奇淫技巧

上面的内容相对比较常规,但是一般面试我们遇到的,都不是常规内容。所以下面这些,是必须掌握的。


下面的这八个技巧,基本cover了位运算90%的面试题:


小浩概念

位运算的奇淫技巧



1、使用 x & 1 == 1 判断奇偶数。(注意,一些编辑器底层会把用%判断奇偶数的代码,自动优化成位运算)

2、不使用第三个数,交换两个数。x = x ^ y , y = x ^ y , x = x ^ y。(早些年喜欢问到,现在如果谁再问,大家会觉得很low)

3、两个相同的数异或的结果是 0,一个数和 0 异或的结果是它本身。(对于找数这块,异或往往有一些别样的用处。)

4、x & (x - 1) ,可以将最右边的 1 设置为 0。(这个技巧可以用来检测 2的幂,或者检测一个整数二进制中 1 的个数,又或者别人问你一个数变成另一个数其中改变了多少个bit位,统统都是它)

5、异或可以被当做无进位加法使用,与操作可以用来获取进位。

6、i+(~i)=-1,i 取反再与 i 相加,相当于把所有二进制位设为1,其十进制结果为-1。

7、对于int32而言,使用 n >> 31取得 n 的正负号。并且可以通过 (n ^ (n >> 31)) - (n >> 31) 来得到绝对值。(n为正,n >> 31 的所有位等于0。若n为负数,n >> 31 的所有位等于1,其值等于-1)

8、使用 (x ^ y) >= 0 来判断符号是否相同。(如果两个数都是正数,则二进制的第一位均为0,x^y=0;如果两个数都是负数,则二进制的第一位均为1;x^y=0 如果两个数符号相反,则二进制的第一位相反,x^y=1。有0的情况例外,^相同得0,不同得1)



03PART两数之和

从最简单的开始讲起。这个题很老了,拿出来给不会的同学看一看,会的直接跳过。(值得一说的是,这个题目在国外上,有2000个dislike,可以看到大家的嫌弃!)

第268题:不使用运算符 + 和 - ,计算两整数 a 、b 之和。


直接使用上面我们讲过的奇淫技巧进行解题:


“异或”是一个无进位加法,说白了就是把进位砍掉。比如01^01=00。

“与”可以用来获取进位,比如01&01=01,然后再把结果左移一位,就可以获取进位结果。


根据上面两个技巧,假设有 12+7:



根据分析,完成题解:


1//JAVA
2class Solution {
3    public int getSum(int a, int b){
4        while(b != 0){
5            int temp = a ^ b;
6            b = (a & b) << 1;
7            a = temp;
8        }
9        return a;
10    }
11}


对,就是这么简单。



04PART2的幂

做这道题前,可以翻到最前面,看一看可以使用哪一个技巧。找到了,你就会了。

第231题:给定一个整数,编写一个函数来判断它是否是 2 的幂次方。


先观察一些是2的幂的二进制数:



可以发现这些数,都是最高位为1,其他位为0。所以我们把问题转化为“判断一个数的二进制,除了最高位为1,是否还有别的1存在”。然后我们再观察下面这样的一组数,对应着上面的数减去1:



我们对两组数求“&”运算:



可以看到,对于N为2的幂的数,都有 N&(N-1)=0 ,所以这就是我们的判断条件。(这个技巧可以记忆下来,在一些别的位运算的题目中也是会用到的)


根据分析,完成代码:


1//go
2func isPowerOfTwo(n int) bool {
3    return n > 0 && n&(n-1) == 0
4}


本题还是很简单。直接使用 x & (x - 1) 的技巧即可。



05PART一的个数

略微增大一点难度,讲这道题目意义是引入一个概念“掩码”。掩码是指使用一串二进制代码对目标字段进行位与运算,屏蔽当前的输入位。

第191题:编写一个函数,输入是一个无符号整数,返回其二进制表达式中数字位数为 ‘1’ 的个数(也被称为汉明重量)。

示例 1:

输入:00000000000000000000000000001011

输出:3

解释:输入的二进制串 00000000000000000000000000001011 中,共有三位为 '1'。


示例 2:

输入:00000000000000000000000010000000

输出:1

解释:输入的二进制串 00000000000000000000000010000000 中,共有一位为 '1'。


示例 3:

输入:11111111111111111111111111111101

输出:31

解释:输入的二进制串 11111111111111111111111111111101 中,共有 31 位为 '1'。


提示:

请注意,在某些语言(如 Java)中,没有无符号整数类型。在这种情况下,输入和输出都将被指定为有符号整数类型,并且不应影响您的实现,因为无论整数是有符号的还是无符号的,其内部的二进制表示形式都是相同的。


在 Java 中,编译器使用二进制补码记法来表示有符号整数。因此,在上面的 示例 3 中,输入表示有符号整数 -3。


题目稍微长了点,但是我之前说过。对于大部分的题而言,题目越长,越简单。


首先最容易想到的方法是:我们直接把目标数转化成二进制数,然后遍历每一位看看是不是1,如果是1就记录下来。通过这种比较暴力的方式,来进行求解。比如Java中,int类型是32位,我们只要能计算出当前是第几位,就可以顺利进行求解。


那如何计算当前是第几位呢,我们可以构造一个掩码来进行,说掩码可能大家听着有点懵逼,其实就是弄个1出来,1的二进制是这样:



我们只需要让这个掩码每次向左移动一位,然后与目标值求“&”,就可以判断目标值的当前位是不是1。比如目标值为21,21的二进制是这样:



然后每次移动掩码,来和当前位进行计算:



根据分析,完成代码:


1//java
2public class Solution {
3    public int hammingWeight(int n) {
4        int result = 0;
5        //初始化掩码为1
6        int mask = 1;
7        for (int i = 0; i < 32; i++) {
8            if ((n & mask) != 0) {
9                result++;
10            }
11            mask = mask << 1;
12        }
13        return result;
14    }
15}


唯一需要提醒的地方是:判断 n&mask 的时候,不要错写成 (n&mask) == 1,因为这里你对比的是十进制数。新人很容易犯这样的错误。



06PART只出现一次的数字

我们再稍微提高一点难度。大家想想用什么思路进行求解?

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


直接分析,我们要找只出现一次的数字,并且已知了其他的数字都只出现了两次。那么这种一听其实就应该想到需使用位运算来进行求解。最好的,就是在读完题目的瞬间,直接条件反射!(当然,如果你现在第一反应是想到 通过遍历统计,或者其他如使用hashmap 等方式来进行求解,那我觉得你的位运算这块,是有必要加强练习力度的。如果你第一反应,连思路都没有,那我觉得对于整个算法的能力这块,都是比较欠缺的,需要下苦功!)


回到题目,如何使用位运算进行求解呢?对于任意两个数a和b,我们对其使用 “异或”操作,应该有以下性质:


  • 任意一个数和0异或仍然为自己:

    a⊕0=a

  • 任意一个数和自己异或是0:

    a⊕a=0

  • 异或操作满足交换律和结合律:

a⊕b⊕a=(a⊕a)⊕b=0⊕b=b


可能有人直接都不知道异或是什么,所以还是举个例子,比如5异或3,也就是5⊕3,也就是5^3,是下面这样:



因为这道题目比较典型,所以我多给几个版本的代码:


(西PP)

1//CPP
2class Solution {
3public:
4    int singleNumber(vector<int>& nums) {
5        int ans = 0;
6        for (int num : nums) {
7            ans ^= num;
8        }
9        return ans;
10    }
11};


(java版本)

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


(python版本)

1//py
2class Solution:
3    def singleNumber(self, nums: List[int]) -> int:
4        ans = 0
5        for i in range(len(nums)):
6            ans ^= nums[i]
7        return ans



07PART只出现一次的数字 Ⅱ

你大爷还是你大爷,但你大妈已经不是你大妈了!

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


使用hashmap来求解的方式,实在是没什么可说的。


1func singleNumber(nums []int) int {
2    m := make(map[int]int)
3    for _, k := range nums {
4        //如果是其他语言,请注意对应的判空操作!
5        m[k]++
6    }
7    for k, v := range m {
8        if v == 1 {
9            return k
10        }
11    }
12    return 0
13}


当然,这里还有一种数学解法:

原理:[A,A,A,B,B,B,C,C,C] 和 [A,A,A,B,B,B,C],差了两个C。


也就是说,如果把原数组去重、再乘以3得到的值,刚好就是要找的元素的2倍。举个例子:



利用这个性质,进行求解:(python代码如下,这里要注意的是,使用int可能会因为超出界限报错)


1class Solution:2    def singleNumber(self, nums: List[int]) -> int:3        return int((sum(set(nums)) * 3 - sum(nums)) / 2)


效果不错,但是仍然使用了额外空间。所以我们还是得使用位运算。对于“每个其余元素,均出现了二次”之所以可以使用“异或”进行求解,原因是因为“异或”操作可以让两数相同归 0。那对于其余元素出现三次的,是不是只要可以让其三者相同归 0,就能达到我们的目的呢?


这个思想可能比较简单,但是要让大家理解,还是有一定难度。如果大家准备好了,可以开始往下看。我看过leetcode上的题解,很多都是直接扔出来一个公式,其实讲的我认为并不是特别的清楚。所以我打算先把本题退化到“每个其余元素,均出现二次”的case来进行分析一下。


假如我们有 [21,21,26] 三个数,是下面这样:



回想一下,之所以能用“异或”,其实我们是完成了一个 同一位上有2个1清零 的过程。上面的图看起来可能容易,如果是这样:



那对于“每个其余元素,均出现了三次”也是一样,如果我们可以完成 一个同一位上的三个1清零的过程,也就是 a ?a ?a = 0,问题则迎刃冰解。那因为各语言中都没有这样一个现成的方法可以使用,所以我们需要构造一个。(想象一下,位运算也是造出来的对不对?)



如何构造,这里先说第一种方法(注意,到这里我们的问题已经转化成了定义一种 a ? a ? a = 0 的运算),观察一下“异或”运算:


1^1=0

1^0=1

0^1=1


是不是可以理解为,其实就是二进制的加法,然后砍掉进位呢?



砍掉进位的过程,是不是又可以理解为对 2 进行取模,也就是取余。到了这里,问题已经非常非常明确了。那我们要完成一个 a ? a ? a = 0 的运算,是不是其实就是让其二进制的每一位数都相加,最后再对 3 进行一个取模的过程呢?(一样,如果要定义一个 a ? a ? a ? a = 0 的运算,那就最后对 4 进行取模就可以了)


1//go
2func singleNumber(nums []int) int {
3    number, res := 00
4    for i := 0; i < 64; i++ {
5        //初始化每一位1的个数为0
6        number = 0
7        for _, k := range nums {
8            //通过右移i位的方式,计算每一位1的个数
9            number += (k >> i) & 1
10        }
11        //最终将抵消后剩余的1放到对应的位数上
12        res |= (number) % 3 << i
13    }
14    return res
15}


如果对上面的代码不能理解,可以看看这个图,假设只有一个数 [21],我们通过不断右移的方式,获取其每一位上的1。当然,这里因为余数都是1,所以肯定都保留了下来,然后与 1 进行 “与”运算,最终再将其放入到对应的位数上。



(还不错)


在上面的代码中,我们通过一个number,来记录每一位数出现的次数。但是缺点是,我们记录了64位(Go语言中,int为32位以上)


(官方文档)


那如果我们可以同时对所有位进行计数,是不是就可以简化过程。因为我们的目的是把每一位与3取模进行运算,是不是就可以理解为其实是一个三进制。如果大家听不懂三进制的话,可以简单理解为3次一循环,也就是 00 - 01 - 10 - 11。但是又因为对于 11 这种情况,我们需要砍掉(上面已经说过了,相当于 11 - 00 的转化),所以我们就只有3个状态,00 - 01 - 10,所以我们采用 a 和 b 来记录状态。其中的状态转移过程如下:



这里 a` 和 b` 的意思代表着 a 和 b 下一次的状态。next 代表着下一个 bit 位对应的值。然后这是什么,不就是状态机嘛。。。我们通过 a 和 b 的状态变化,来完成次数统计。


然后因为此图复杂,将其分别简化成 a 和 b 的卡诺图(卡诺图是逻辑函数的一种图形表示。两逻辑相邻项,合并为一项,保留相同变量,消去不同变量。)


next\a,b00011110
110X0
001X0


next\a,b00011110
101X0
000X1


然后我们根据卡诺图(这个卡诺图其实并不难看。。如果学习一下话,还是挺简单的。。)写出关系式:


a` = (a &~ next) | (b & next)

b` = (~a & ~b & next) | (b & ~next)


然后就是套公式:(Java代码,注意Go语言中是不天然支持 ~ 这种运算的)


1class Solution {
2    public int singleNumber(int[] nums) {
3        int a = 0, b = 0, tmp = 0;
4        for (int next : nums) {
5            tmp = (a & ~next) | (b & next);
6            b = (~a & ~b & next) | (b & ~next);
7            a = tmp;
8        }
9        return b;
10    }
11}


当然,其实题解还可以再近一步优化,其实就是化简上一步中的公式:


1class Solution {
2    public int singleNumber(int[] nums) {
3        int a = 0, b = 0;
4        for (int next : nums) {
5            b = (b ^ next) & ~a;
6            a = (a ^ next) & ~b;
7        }
8        return b;
9    }
10}


当然,这个解法就相当牛皮了。如果实在看不懂也没关系,请把上面的两种解法掌握。



08PART啰嗦一下

位运算的常考点上面的题目基本上都覆盖了,还是希望大家下去自己练习一番。




推荐阅读

•   C++是如何从代码到游戏的?•   告诉你一个学习编程的诀窍(建议收藏)•   自学编程的八大误区!克服它!•   新手如何有效的刷算法题(LeetCode)•   10款VS Code插件神器,第7款超级实用!•   在拼多多上班,是一种什么样的体验?我tm心态崩了呀!•   写给小白,从零开始拥有一个酷炫上线的网站!


欢迎关注我的公众号“五分钟学算法”,如果喜欢,麻烦点一下“在看”~

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存