阅读 260

全面了解位运算与硅谷面试题

前言

本篇文章浅谈位运算符、二进制、机器数的原码、反码、补码以及位运算的应用,最后附上吴军老师提到过的硅谷面试题,希望阅读完本篇文章的同学,熟练掌握二进制与位运算,leetcode刷到爆。

位运算符

按位运算符将其操作数视为32位(0和1)的序列,而不是十进制,十六进制或八进制数。例如,十进制数字9 具有1001的二进制表示。按位操作符操作数字的二进制形式,但返回值依然是标准的JavaScript数值。

七种运算方式

下面的表格总结了JavaScript中的按位操作符

运算符 用法 描述
与(&) a & b 当两个操作数相对应的位都为1时,结果才为1,否则为0。
或(|) a | b 当两个操作数相对应的位至少有一个为1时,结果为1,否则为0。
异或(^) a ^ b 当两个操作数相对应的位只有一个为1时,结果为1,否则为0。
取反(~) ~ a 反转操作数的位,即0变成1,1变成0。
左移(<<) a << b 将 a 的二进制形式向左移 b (< 32) 位,右边用0填充。
右移(>>) a >> b 将 a 的二进制表示向右移 b (< 32) 位,丢弃被移出的位。
零填充右移(>>>) a >>> b 将 a 的二进制表示向右移 b (< 32) 位,丢弃被移出的位,并使用 0 在左侧填充。

在讲位运算之前,先简要讲述一下机器数的形式原码、反码、补码

什么是机器数?

机器数是将符号"数字化"的数,是数字在计算机中的二进制表示形式。在通常的运算中,用“+”、“-”表示正数和负数,而数字电路不识别“+”,“-”。因此,在数字电路中把一个数的最高位作为符号位,并用0表示“+”,用1表示“-”。

原码

首位为符号位,0表示整数,1表示负数,其余位表示数值。

例如0000 0011表示+3,而1000 0011表示-3。

  • 原码中0有两种表现形式,中+0为 0000 0000,-0为 1 000 0000

问题来了,在原码中(+3)+(-3) = 0 吗?0000 0011 + 1000 0011 = 1000 0110 为-6的错误结果,显然这个结果并不是我们想要的。如果解决原码中正负相加的问题呢?反码

反码

如果是正数,则表示方法和原码一样;如果是负数,符号位不变,其余各位取反。

例如 -3原码为 1000 0011,反码为1111 1100

0000 0011 + 1111 1100 = 1111 1111 为-0,解决上面原码遇到的问题,但是新问题来了,反码中0依然有两种表现方式,0000 0000(+0)和 1111 1111(-0)。这时出现了补码

补码

如果是正数,则表示方法和原码一样;如果是负数,则将数字的反码未位加1(相当于将原码数值位取反后未位加1)

例如 -3反码为1111 1100,其补码为1111 1101

0000 0011 + 1111 1101 = 0000 0000(+0)
复制代码

重述一遍,补码保证了当一个数是正数时,其最左的bit位是0,当一个数是负数时,其最左的bit位是1。因此,最左边的bit位被称为符号位。

为什么会有原码,反码,补码?

计算机采用二进制表示数,那么具体如何表示其中也是有学问的。原码是人类最直观想到的表现方式,但原码有缺点,于是产生了反码,反码也有缺点,最后产生了相对合理补码,于是计算机系统大多使用补码来存储二进制数。反码的作用主要是方便原码到补码的过渡,方便理解。 如果只有加法和正数,那么使用原码没有什么问题。之所以出现反码、补码,正是为了解决负数和减法所带来的问题。所以正数的原码、反码、补码都是一样的。

如果想对原码、反码、补码有更深的了解,推荐读《计算机原理》这本书,这里就不再赘述了。

有符号32位整数

0 是所有bit数字0组成的整数。

// 十进制 = 二进制

0 = 0000 0000 0000 0000 0000 0000 0000 0000
复制代码

-1 是所有bit数字1组成的整数。

-1 = 1111 1111 1111 1111 1111 1111 1111 1111
复制代码

-2147483648(十六进制形式:-0x80000000)是除了最左边为1以外,其他bit位都为0的整数。

-2147483648 = 1000 0000 0000 0000 0000 0000 0000 0000
复制代码

2147483647(十六进制形式:0x7fffffff)是除了最左边为0以外,其他bit位都为1的整数。

2147483647 = 0111 1111 1111 1111 1111 1111 1111 1111
复制代码
  • 所以 **数字-2147483648 和 2147483647 是32位有符号数字所能表示的最小和最大整数。**这里可能会成为考点。

下面讲一下位运算符

& (按位与)

当两个操作数相对应的位都为1时,结果才为1,否则为0。

举个例子,7 & 4 (默认例子按照8bit展示)

7 = 0000 0111 
4 = 0000 0100

-------------

7 & 4 = 0000 0100  => 4
复制代码

再举一个例子,7 & -4(关于负数在上面机器数中有介绍)

7 = 0000 0111 
-4 = 1111 1100

-------------

7 & -4 = 0000 0100 => 4
复制代码

| (按位或)

当两个操作数相对应的位至少有一个为1时,结果为1,否则为0。

举个例子,7 | 4

7 = 0000 0111 
4 = 0000 0100

-------------

7 | 4 = 0000 0111  => 7
复制代码

^ (按位异或)

当两个操作数相对应的位只有一个为1时,结果为1,否则为0。

举个例子,7 ^ 4

7 = 0000 0111 
4 = 0000 0100

-------------

7 ^ 4 = 0000 0011  => 3
复制代码

~ (按位非)

反转操作数的位,即0变成1,1变成0。

举个例子,~ 3

3 = 0000 0011 

-------------

~ 3 = 1111 1100  => -4

复制代码
  • ~ 小技巧

根据~运算符,~ -1等于0我们可以把以下代码进行优化

const arr = ['a', 'b', 'c']

// if (arr.indexOf('d') > -1) { 这里也可以用includes代替
if (~arr.indexOf('d')) 
   // 存在
} else {
   // 不存在
}
复制代码

~~取整

const num = 3.14

~~num // 3 原理根据位运算基于整数进行计算
复制代码

<< (左移)

将 a 的二进制形式向左移 b 位,右边末尾用0填充。

举个例子,7 << 2

7 = 0000 0111

-------------

7 << 2 = 0001 1100  => 28
复制代码

这里说一下数字溢出,当二进制数的位数超过了系统所指定的位数。 上面我们说到32位有符号数字最小值为-2147483648,二进制为1后面31个0,当我们将它进行左移后结果是什么呢?大家可以试试。

>> (右移)

将 a 的二进制表示向右移 b 位,丢弃被移出的位。

举个例子,7 >> 2

7 = 0000 0111 

-------------

7 >> 2 = 0000 0001  => 1
复制代码

-7 >> 2(32bit)


-7 = 1111 1111 1111 1111 1111 1111 1111 1001

-------------

-7 >> 2 = 1111 1111 1111 1111 1111 1111 1111 1110 => -2

复制代码

>>>(零填充右移)

将 a 的二进制表示向右移 b 位,丢弃被移出的位,并使用 0 在左侧填充。

举个例子,7 >>> 2

7 = 0000 0111 

-------------

7 >>> 2 = 0000 0001  => 1
复制代码
  • -7 >>> 2 (与 >> 的区别)
-7 = 1111 1111 1111 1111 1111 1111 1111 1001

-------------

-7 >>> 2 = 0011 1111 1111 1111 1111 1111 1111 1110  => 1073741822
复制代码

几种运算方式到这里就简单的讲完了,我们结合原理来做几道面试题。

常见进制以及位运算面试题

第一题

二进制中1的个数

问题:请实现一个函数,输入一个整数,输出该二进制表示中1的个数。例如把9表示为二进制是1001,有2位是1。因此输入9时,该函数返回2。

(5秒后公布答案) .

.

.

.

.

.

.

解法1:右移

function method (n) {
  var count = 0
  while (n) {
     if (n & 1) count++

     n = n >> 1
  }
  return count
}
复制代码

该方法有一个重大的缺陷,当n为负数时,将会陷入无限循环。原因是位移前为负数,位移后仍然要保持为负数,因此位移后最高位会是1。假如一直向右位移,最终数字永远为-1。如何修复这个缺陷呢?这里我给出一个非官方解法2

解法2:零填充右移

function method (n) {
  var count = 0
  while (n) {
     if (n & 1) count++

     n = n >>> 1
  }
  return count
}
复制代码

乍一看没啥区别,只是把右移换成了零填充右移。细心的同学已经猜到了,上面我有说位移要保持正负值不变,因此负数的最高位会是1,这一点导致了无限循环。那么我们把最高位1换成0不就可以了么!零填充右移(>>>)恰恰满足了需求。

解法3:左移

function method (n) {
  var count = 0
  var flag = 1
  while (flag) {
    if (n & flag) count++
    flag = flag << 1
  }
  return count
}
复制代码

flag值不断地左移与n值做与操作,大于0表示为1,反之为0。这个解法存在一个缺陷,就是循环的次数等于整数二进制的位数,32位整数需要循环32次。

解法4:减1与

function method (n) {
  var count = 0
  while (n) {
    ++count
    n = (n - 1) & n
  }
  return count
}
复制代码

该方法循环次数与二进制1的个数相等。这个解法我详细分解一下过程。n分为3种,正数、负数和零。

  1. 当n为0时,count为0
  2. 当n为正数时,打个比方n为9,9的二进制为1001,进入循环 count + 1,(n - 1) & n这里我们分解为二进制 1000 & 1001,上面有说过与操作符含义是当两个操作数相对应的位都为1时,结果才为1,否则为0。所以这里n等于1000,十进制为8。n不等于0,继续进入循环,count + 1,然后 n = 0111 & 1000,n等于0,结束循环。count等于2。
  3. 当n为负数时,打个比方n为-1,二进制就是32个1,-2的二进制是31个1,末尾一个0,以此类推。接下来我们分析过程,n为-1时,n不为零,count + 1,n = -2 & -1,n为-2,重新循环,...(中间过程省略),循环到第32次,-2147483649 & -2147483648 为 0,上面提到32位最小值为-2147483648,-2147483649属于数字溢出,在32位二进制表示是32个0。所以最终结果为0。

第二题

在Excel中,用A表示第1列,B表示第2列...Z表示第26列,AA表示第27列,AB表示第28列以此类推。请写一个函数,输入用字母表示的列号码表,输出它是第几列。

(5秒后公布答案) .

.

.

.

.

.

.

function method (str) {
  let num = 0
  const arr = str.split('')
  for (let len = str.length - 1, i = len, j = 1; i >= 0; i--, j *= 26) {
    let s = str[i].toUpperCase()
    if (!/[A-Z]/.test(s)) {
      return 0
    }
    num += (s.charCodeAt(0) - 64) * j
  }
  return num
}
复制代码

分析:将字符串转换为数组,方便遍历。将A到Z的字符转换为Unicode编码,已知A的Unicode编码为65,如题A为1,所以减64。设定一个值j,基数为26的n次方。每循环一次n + 1,这里用 j *= 26 方式代替,也可以使用Math.pow方法。

第三题

如上题请写一个函数,当输入第几列,返回字母表示的列号码表。

(5秒后公布答案) .

.

.

.

.

.

.

function method (num) {
  let str = ''
  while (num > 0) {
    let r = num % 26
    if (!r) {
      r = 26
    }
    str += String.fromCharCode(r + 64)
    num = (num - r) / 26
  }
  return str
}
复制代码

分析:判断值是否大于0,取余数、指定Unicode值得到字符串。

附加:硅谷面试题

有64瓶药,其中63瓶是无毒的,一瓶是有毒的。如果做实验的小白鼠喝了有毒的药,3天后会死掉,当然喝了其它的药,包括同时喝几种就没事。现在只剩下3天时间,请问最少需要多少只小白鼠才能试出那瓶药有毒?

(5秒后公布答案) .

.

.

.

.

.

.

答案:六只小老鼠

  1. 我们将这些药从0~63按照二进制编号,获得64个六位数的二进制编号,也就是从000000(六个零)到111111(六个一),每个二进制编号的最左边是第一位,最右边是第六位。

  2. 然后选六只老鼠从左到右排开,和二进制的六位,从左到右地依次对应。文稿里的二进制编号,你可以试着一位一位竖着看,下面每只老鼠负责一位。

  3. 从左边数第一个老鼠吃对应的二进制是1的药,0就不吃。那么老鼠1依次吃第32,33,34,……,63号药。第二只吃16,17,……,31,48,49,……,63号药,等等。最后一只老鼠吃1,3,5,……,63号药。你可能注意到了,6只老鼠都吃了63号,那是因为63对应的二进制编号是6个1,所以6只都要吃。

  4. 吃完药之后三天,某些老鼠可能死了,我们假定第1,2,6这三只老鼠死了,剩下的活着。这说明什么呢?说明编号110001号药有问题,也就是在第1,第2,第6位上分别是3个1,因为这三只老鼠都吃了它,而3,4,5这三只没死的老鼠没有吃它(对应的位置为0)。而110001对应十进制的49,也就是说第49瓶药是毒药。

对于其它的组合也是同样的,你可以自己随便假定哪几只老鼠死了,看看哪瓶是毒药。当然,还有一种情况,就是所有的老鼠都没有死,那说明第0号药是毒药,因为其他的药都吃过了,就这一瓶没有吃。

结语

关于位运算的基本运算方式和面试题就讲到这里,如果你有更经典、有趣的面试题,不妨分享出来。一起讨论,欢迎留言。

其他链接

Vue UI组件库从1到N开发心得-组件篇

Vue UI组件库从0到1开发心得

Github

祝工作顺利

邓文斌

2019年6月6日

关注下面的标签,发现更多相似文章
评论