likes
comments
collection
share

面试官:如何实现高效的乘法【位运算详解】

作者站长头像
站长
· 阅读数 4

计算机的底层数据都是二进制,二进制运算就是位运算,今天就带大家一起复习下

身为一个程序员,哪怕你是个前端,大概率用不上这些,但是这些知识你就是得清楚

位运算包括与&或|异或^非~等等

计算机里面只有开和关两种状态,开就是1,关就是0,所有数据最终都会被转换成二进制,像计算机这样用二进制表示信息就是二元系统

实际生活中我们都是用十进制来表示信息,因此这里就涉及一个进制的转换问题

进制转换

十进制转二进制

13
// 13 / 2 = 6   1
// 6  / 2 = 3   0
// 3  / 2 = 1   1
// 1  / 2 = 0   1
// 13的二进制就是1101

像这样,将给定的十进制除以2,记录下商和余数,再将得到的商再次除以2,重复此过程,直到商为0,最后所得的二进制就是余数按照相反的顺序排列起来

二进制的规则如下

x * 2 ^ n + x * 2 ^ (n-1) + …… + x * 2 ^ 0 = 13

二进制转十进制

1101
// 1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0 = 13

像这样,从二进制数的最右边(最低位)开始,每一位数字乘以2的幂,幂的指数从0开始递增,对每一位的乘积进行累加,得到最终的十进制数

js自带一个parseInt方法可以进行进制转换,这个方法定义在全局中

parseInt()

这个方法有两个参数,第二个参数可选,如果不用第二个参数,并且传入小数进去,起到一个向下取整的作用

console.log(parseInt(2.3))  // 2
console.log(parseInt(2.7))  // 2

等同于Math.floor()向下取整

当我们用到第二个参数时,第二个参数默认为10,这个参数表示,第一个参数是几进制,并且最终将其输出为10进制

console.log(parseInt(1101, 10)) // 1101
console.log(parseInt(1101, 2))  // 13

来个面试题

这道面试题当年出现时非常火,因为太恶心人了

const arr = [1, 2, 3]
const newArr = arr.map(parseInt)
console.log(newArr)

分析下第二行代码:map本身接受一个回调函数,这里直接将parseInt作为其回调函数,map会返回一个新数组,其实这行代码就相当于arr.map((item, i => parseInt(item, i)))map的回调按道理是有三个值,分别为:当前元素的值,当前元素的下标,数组本身。但是parseInt只接受两个参数,只取前两个,因此循环三遍

parseInt(1, 0) // 放0跟没放一样 所以就是10  就是1
parseInt(2, 1) // 放1,但是没有1进制  就是Not a Number NaN
parseInt(3, 2) // 3无法看成2进制  NaN

第二个参数在mdn上有解释,放0等于没放,没放就是默认为10

输出[ 1, NaN, NaN ]

位运算

所有的位运算方法都是为二进制服务,因此不要在十进制中出现位运算

位运算有个非常常见的考点,不要用乘号进行两数相乘,稍后解答

按位与(&)

将两个数字的二进制的每一位进行 & 操作,相应位都为1则为1,否则为0

const num1 = 5  // 101 
const num2 = 3  // 011
const num3 = 6  // 110

console.log(num1&num3)  // 结果为100 输出4

当两个二进制长度不等时,可以在前面补0,101和110对位相与,得100,输出为4

我们要清楚,v8引擎呈现给我看的数字一定是十进制

如何判断一个整数是否为2的幂次方

这个问题如果用与来解决就非常巧妙,我们先观察一下2的幂次方的这些数,二进制都有什么特点

2 = 10  4 = 100 8 = 1000  16 = 10000

除了最高位,其余全部为0,因此,如果给这些数都减一个1,那么得到的将会是如下这样

2-1 = 01  4-1 = 011  8-1 = 0111  16-1 = 01111 

将幂次方的数,相与减1之后的数,全部为0,这就是规律,因此题解如下

const num = 15
function isPower(num) {
    if (num > 0) {
        return (num & (num - 1)) === 0
    }
    return false
}
console.log(isPower(num))

当面试官问你关于数字的面试题,想不到的时候你就可以试着往二进制去思考

按位或(|)

将两个数字的二进制的每一位进行 | 操作,相应位全为0 才为0

const num1 = 5  // 101
const num2 = 3  // 011

console.log(num1 | num2)  // 111  7

101和011对位或,有1就为1,全0才0,得111,输出十进制7

按位异或(^)

将两个数字的二进制的每一位进行 ^ 操作,相应位相同为0 不同为1 异或就是不同的或,不同才为1

这个东西通常用于数据加密和校验

let num1 = 5  // 101
let num2 = 3  // 011

console.log(num1 ^ num2)  // 110   6

101和011进行异或操作,不同才为1,得110为6

如何交换两个数的值,而不使用额外的变量

es6提供了解构的语法,[num1, num2] = [num2, num1],但是这里我们不考虑这种,而用位运算

同样非常巧妙,我们不妨将两个数异或两次,比如

// 5    101
// 7    111  
//      010   异或
//      101   再次异或发现回到101
//      111   再次异或发现回到111

因此题解如下

let num1 = 5  // 101
let num2 = 3  // 011

function swap(a, b) {
    a = a ^ b
    b = a ^ b
    a = a ^ b
    return [a, b]
}
[num1, num2] = swap(num1, num2)

console.log(num1, num2) // 3 5

按位非(~)

将一个数字的二进制的每一位进行 ~ 操作,0变成1 1变成0 将得到的值转成32位

const num = 5 // 00000000 00000000 00000000 00000101

console.log(~num)  // 11111111 11111111 11111111 11111010  -6

对5转换成二进制,然后将其长度补至32位,然后每一位都取反,得到的数其实就是-6,如果你去算,可能算的结果是个很大的十进制数,这是因为现在的计算器都是64位,也就是说补到了64位,按32位算,第一位符号位,0代表正数,1代表负数

面试官:如何实现高效的乘法【位运算详解】

点击QWORD,降至32位

面试官:如何实现高效的乘法【位运算详解】

为何11111111 11111111 11111111 11111010的十进制表示-6呢,这就需要提到补码这个概念

补码

补码是一种用于表示有符号整数的编码方式,在补码表示法中,正整数的二进制表示与无符号整数的二进制表示相同,这也就可以解释,刚刚全是正数,无需提及这个概念。负整数的二进制表示则通过对其对应的正整数的二进制表示取反,然后+1得到

所以11111111 11111111 11111111 11111010的十进制表示-6

我们要求-6的二进制数,就是求它的补码,那么就是求6的二进制,先取反,然后+1,得其补码

这里只写八位做演示

let n = -6  // 00000110
            // 11111001 + 1 取反加1
            // 11111010 
console.log(~n) // 5

只看八位,那么11111010就表示-6,如果对其取反,就是0000101,就是5

~~a

我们经常看到有些大佬的代码写成比如这样

let a = 2.3
console.log(~~a) // 2

一个变量前面打两次非,最终的效果就是一个向下取整

为什么两次取非会有向下取整的效果?

我们顺便看下小数转二进制,其过程如下

  1. 小数部分乘以2,取结果的整数部分作为二进制的第一位
  2. 取剩余的小数部分,再次乘以2,取结果的整数部分作为二进制的第二位
  3. 以此类推,不断重复这个过程,直到小数部分为0或者达到所需精度
  4. 顺序排列
0.625转二进制
// 0.625 * 2 = 1.251
// 0.25 * 2  = 0.50
// 0.5 * 2   = 1.01
二进制为0.101

因此~~2.3为

2.3 // 00000010.010001……
0.3 * 2 = 0.60
0.6 * 2 = 1.21
0.2 * 2 = 0.40
0.4 * 2 = 0.80
0.8 * 2 = 1.61
…………
~2.3  // 11111101.101110
~~2.3 // 00000010.010001

因此整数位二进制为10,也就是2,由于js的位运算处理的是32位整数,小数位会被截断,因此得到一个向下取整的效果

其实取整和小数位二进制无关,只是因为两次取非,数据不变,但是把小数给截断了

左移(<<)和右移(>>)

左移:将一个数的二进制位向左移动指定的位数,右侧空出的位置用0填充

右移:将一个数的二进制位向有移动指定的位数,左侧空出的位置根据情况用0或者1填充,正数用0,负数用1。无符号右移就是补0,专门用>>>符号表示

左移右移在二进制算法中考到的频率是最高的,面试到的概率也很大

const num = 5 // 00000101
            //   00010100
            //      16 + 4  左移两位
            //   00000001   右移两位
console.log(num << 2)  // 20
console.log(num >> 2)  // 1

5的二进制左移两位,就是10100,右移两位,就是1,分别打印出十进制

如何实现一个高效率的整数乘法

这是个面试经典题,既然是高效率一定会非常底层,*没有二进制实现来得效率高,那么问题来了,如何用位运算实现十进制相乘呢

位运算要考,这个题目考的概率最大

其实左移一位就是乘以一次2,上面的5左移了两位就是乘了两次2,也就是20,而右移就相当于除以2,由于可能产生小数,因此截断小数,右移就是除以2并向下取整

非常巧妙,xy相乘,不断左移x,右移y,左移x就是让x乘以2,右移y就是让y除以2并向下取整,在y大于0的条件下循环,只要y的二进制最后一位是1,就累加此时的x

function multiply (x, y) {
    let result = 0
    while (y > 0) {
        if (y & 1) {  // 判断y二进制的最低位是否为一
            result += x
            // 5
            // 5+10   
        }
        x = x << 1
        y = y >> 1
    }
    return result
}

console.log(multiply(5, 3))

比如5 * 35 * 4如下

5 * 3
// 00000101 * 00000011
// 011大于0 并且011&1为1 result = 5
// 5左移一位 3右移一位 00001010  00000001
// 此时01大于0 并且01&1为1 result = 5 + x  此时x为1010 也就是10 result = 15
// 5左移一位 3右移一位 00010100  00000000
// 循环终止 返回 15 
5 * 4
// 00000101 * 00000100
// 100大于0 但100最低位为0 不走if
// 5左移 4右移 00001010 00000010
// 10大于0 但10最低位为0 不走if
// 5左移 4右移 00010100 00000001
// 1大于0 满足if result = x 此时x = 10100 也就是20
// 5左移 4右移 00101000 00000000
// 终止循环 返回20

高效实现一个除法会比乘法难很多,有大佬知道可以在评论区分享下

最后

本期文章主要带大家复习了下关于位运算的内容,面试中也是比较容易考到这些

另外有不懂之处欢迎在评论区留言,如果觉得文章对你学习有所帮助,还请”点赞+评论+收藏“一键三连,感谢支持!

本次学习代码已上传至本人GitHub学习仓库:github.com/DolphinFeng…

转载自:https://juejin.cn/post/7331070678693232666
评论
请登录