常考算法题解析

常考算法题解析

位运算

左移<<

console.log(10 << 1);//20

左移就是将二进制全部往左移动一位。10在二进制中表示1010，左移一位后变成10100，转换为十进制也就是20，所以基本可以把左移看成一下公式，a * (2 ^ b)。

右移>>

console.log(10 >> 1);//5
console.log(13 >> 1);//6

右移就是将二进制全部右移并去除多余的右边。10在二进制中表示为1010，右移一位后变成101，转换为十进制就是5，所以基本可以把右移看成一下公式v = a / (2 ^ b)。

按位操作

按位与

每一位都为1，结果才为1

console.log(8 & 7);// 1000 & 0111 -> 0000 -> 0

按位或

其中一位为1，结果就是1

console.log(8 | 7);// 1000 | 0111 -> 1111 -> 15

按位异或

每一位都不同，结果才为1

console.log(8 ^ 7);// 1000 ^ 0111 -> 1111 -> 15
console.log(8 ^ 8);// 1000 ^ 1000 -> 0000 -> 0

面试题

两个数不使用四则运算得出和

function sum(a, b) {
  if (a == 0) return b
  if (b == 0) return a
  let newA = a ^ b
  let newB = (a & b) << 1
  return sum(newA, newB)
}
console.log(sum(1,2));//3

排序

以下两个函数是排序中会用到的通用函数，就不一一写了

function swap(array, left, right) {
    let rightValue = array[right]
    array[right] = array[left]
    array[left] = rightValue
}

swap函数也可以这样写

function swap(array, left, right) {
    [array[left], arrar[right]] = [array[right], array[left]];
}

冒泡排序

function bubble(array){
  for(let i = array.length - 1;i > 0; i-- ){
    for(let j = 0; j < i; j++){
      if(array[i] < array[j])swap(array,j,j+1);
    }
  }
  return array;
}
console.log(bubble([2,3,6,1,3,5,2]));