位运算

行者、空山/2020-12-25 15:50

38 min read

Get Bit

该方法向右移动目标位到最右边，即位数组的第0个位置上。然后在该数上与形如 0001的二进制形式的数进行ADD操作。这会清理掉除了目标位的所有其它位的数据。如果目标位是1，那么结果就是1，反之，结果是0;

const getBit = (num,bitPosition)=>{
  return ((num >> bitPosition) & 1);
};

Set Bit

该方法把1向左移动了bitPosition位，生成了一个二进制形如00100的值。然后我们拿该值与目标数字进行OR操作，就能把目标位设置位1而不影响其它位。

const setBit = (num,bitPosition)=>{
  return ((1 << bitPosition) | num );
};

Clear Bit

该方法把1向左移动了bitPosition位，生成了一个二进制形如00100的值。然后反转每一位的数字，得到一个二进制形如11011的值。接着与目标值进行ADD操作，就能清除掉目标位的值。

const clearBit = (num,bitPosition)=>{
  const mask = ~(1<<bitPosition);
  return mask & num;
};

Update Bit

该方法组合了“Clear Bit”和“Set Bit”

const updateBit = (num,bitPosition,bitValue)=>{
  const bitValueNormalized = bitValue ? 1 : 0;
  const tmp = clearBit(num,bitPosition);
  return setBit(tmp,bitValueNormalized); 
};

isEven

该方法检测传入的number是否是偶数。它的实现基于奇数的最右边的位永远是1这个事实。

Number: 5 = 0b0101
isEven: false

Number: 4 = 0b0100
isEven: true

const isEven = (num)=>{
  return (num & 1) === 0;
};

isPositive

该方法检测传入的number是否是正数。它的实现基于正数最左边的位永远是0这个事实。然而如果传入的number是0或者-0，它也应该返回false。

Number: 1 = 0b0001
isPositive: true

Number: -1 = -0b0001
isPositive: false

const isPositive = (num)=>{
  if(num === 0)return false;
  // js位运算 最多支持32位有符号数
  return ((num>>31) & 1) === 0;
};

Multiply By Two

该方法将原始数字向左移动一位。因此所有位都将乘以2，因此数字本身也将乘以2。

Before the shift
Number: 0b0101 = 5
Powers of two: 0 + 2^2 + 0 + 2^0

After the shift
Number: 0b1010 = 10
Powers of two: 2^3 + 0 + 2^1 + 0

const multiplyByTwo = (num)=>{
  return num << 1;
};

Divide By Two

该方法将原始数字向右移动一位。因此所有位都将除以2，因此数字本身也将除以2,且不会产生余数。

Before the shift
Number: 0b0101 = 5
Powers of two: 0 + 2^2 + 0 + 2^0

After the shift
Number: 0b0010 = 2
Powers of two: 0 + 0 + 2^1 + 0

const divideByTwo = (num)=>{
  return num >> 1;
};

Switch Sign

该方法将正数变成负数，反之亦然。为了做到这一点，它使用了“二进制补码”的方法，即取反所有位然后加1.

const switchSign = (num)=>{
  return ~num + 1;
};

Multiply Two Signed Numbers

该方法使用位运算符计算两个有符号数的乘积。实现基于以下事实：

a * b 可以被改写成如下形式:
  0                     a为0，b为0，或者a，b都为0
  2a * (b/2)            b是偶数
  2a * (b - 1)/2 + a    b是奇数，正数
  2a * (b + 1)/2 - a    b是奇数，负数

这样转换的优势在于，递归的每一步，递归的操作数的值都减少了一半。因此，运行时的时间复杂度为O(log(b)),其中b是在每个递归步骤上减少为一半的操作数。

const multiply = (a,b)=>{
  if( a === 0 || b === 0){
    return 0;
  }
  if(isEven(b)){
    return multiply(multiplyByTwo(a),divideByTwo(b));
  }else if(isPositive(b)){
    return multiply(multiplyByTwo(a),divideByTwo(b-1))+a;
  }else{
    return multiply(multiplyByTwo(a),divideByTwo(b+1))-a;
  }
};

Multiply Two Unsigned Numbers

该方法使用位运算符计算两个无符号数的乘积。实现基于“每个数字都可以表示为一系列2的幂的和”。

逐位乘法的主要思想是，每个数字都可以拆分为两个乘方的和：

比如：

19 = 2^4 + 2^1 + 2^0

然后19乘x就等价于：

x * 19 = x * 2^4 + x * 2^1 + x * 2^0

接着我们应该意识到x*2^4是等价于x向左移动4位（x << 4）的;

const multiplyUnsigned = (a,b)=>{
  let result = 0;
  let bitIndex = 0;
  let multiplier = b;
  while(multiplier!=0){
    if(multiplier & 1){
      result += (a << bitIndex);
    }
    bitIndex += 1 ;
    multiplier >>= 1;
  }
  return result;
};

Count Set Bits

该方法使用位运算符对一个数字里设置为1的位进行记数。主要方法是，把数字每次向右移动1位，然后使用&操作符取出最右边一位的值，1则记数加1，0则不计。

Number: 5 = 0b0101
Count of set bits = 2

const countSetBits = (num)=>{
  let count = 0;
  while(num!=0){
    if(num & 1){
      count+=1;
    }
    num >>>= 1;
  }
  return count;
};

Count Bits to Flip One Number to Another

该方法输出把一个数字转换为另一个数字所需要转换的位数。这利用了以下特性：当数字进行XOR异或运算时，结果将是不同位数的数量(即异或的结果中所有被设置为1的位的数量)。

5 = 0b0101
1 = 0b0001
Count of Bits to be Flipped: 1

const bitsDiff = (num1,num2)=>{
  return countSetBits(num1 ^ num2);
};

Count Bits of a Number

为了计算数字的有效位数，我们需要把1每次向左移动一位，然后检查产生的值是否大于输入的数字。

5 = 0b0101
有效位数: 3
当我们把1向左移动4位的时候，会大于5.

const bitLength = (num)=>{
  let bitCount = 0;
  while( num >= (1<<bitCount)){
    bitCount += 1;
  }
  return bitCount;
};

Is Power of Two

该方法检测数字是否可以表示为2的幂。它使用了以下特性，我们定义powerNumber是可以写成2的幂的形式的数(2,4,8,16 etc.)。然后我们会把powerNumber和powerNumber - 1进行&操作，它会返回0(如果该数字可以表示为2的幂)。

Number: 4 = 0b0100
Number: 3 = (4 - 1) = 0b0011
4 &amp; 3 = 0b0100 &amp; 0b0011 = 0b0000 &lt;-- Equal to zero, is power of two.

Number: 10 = 0b01010
Number: 9 = (10 - 1) = 0b01001
10 &amp; 9 = 0b01010 &amp; 0b01001 = 0b01000 &lt;-- Not equal to zero, not a power of two.

const isPowerOfTwo = (num)=>{
  return (num & (num - 1)) ? false : true; 
};

Full Adder

该方法使用位运算符计算两个数的和。

它实现了完整的加法器电子电路逻辑，以补码的形式计算两个32位数字的和。它使用布尔逻辑来覆盖了两个位相加的所有情况：从前一位相加的时候，产没产生进位“carry bit”。

Legend:

A: 数字 A
B: 数字 B
ai: 数字A以二进制表示时的位下标
bi: 数字B以二进制表示时的位下标
carryIn: 本次计算产生的进位
carryOut: 带入此次计算的进位
bitSum: ai, bi, 和 carryIn 的和
resultBin: 当前计算的结果（二进制形式）
resultDec: 当前计算的结果（十进制形式）

A = 3: 011
B = 6: 110
┌──────┬────┬────┬─────────┬──────────┬─────────┬───────────┬───────────┐
│  bit │ ai │ bi │ carryIn │ carryOut │  bitSum │ resultBin │ resultDec │
├──────┼────┼────┼─────────┼──────────┼─────────┼───────────┼───────────┤
│   0  │ 1  │ 0  │    0    │    0     │     1   │       1   │     1     │
│   1  │ 1  │ 1  │    0    │    1     │     0   │      01   │     1     │
│   2  │ 0  │ 1  │    1    │    1     │     0   │     001   │     1     │
│   3  │ 0  │ 0  │    1    │    0     │     1   │    1001   │     9     │
└──────┴────┴────┴─────────┴──────────┴─────────┴───────────┴───────────┘

const fullAdder = (a,b)=>{

  let result = 0;
  let carry = 0;

  // js位运算 最高32位
  for (let i = 0; i < 32; i += 1) {
    const ai = getBit(a, i);
    const bi = getBit(b, i);
    const carryIn = carry;

    const aiPlusBi = ai ^ bi;

    const bitSum = aiPlusBi ^ carryIn;

    const carryOut = (aiPlusBi & carryIn) | (ai & bi);
    carry = carryOut;

    result |= bitSum << i;
  }

  return result;
};

查看Full Adder on YouTube.

完整的代码

(()=>{

  const getBit = (num,bitPosition)=>{
    return ((num >> bitPosition) & 1);
  };
  const setBit = (num,bitPosition)=>{
    return ((1 << bitPosition) | num );
  };
  const clearBit = (num,bitPosition)=>{
    const mask = ~(1<<bitPosition);
    return mask & num;
  };
  const updateBit = (num,bitPosition,bitValue)=>{
    const bitValueNormalized = bitValue ? 1 : 0;
    const tmp = clearBit(num,bitPosition);
    return setBit(tmp,bitValueNormalized); 
  };
  const isEven = (num)=>{
    return (num & 1) === 0;
  };
  const isPositive = (num)=>{
    if(num === 0)return false;
    // js位运算 最多支持32位有符号数
    return ((num>>31) & 1) === 0;
  };
  const multiplyByTwo = (num)=>{
    return num << 1;
  };
  const divideByTwo = (num)=>{
    return num >> 1;
  };
  const switchSign = (num)=>{
    return ~num + 1;
  };
  const multiply = (a,b)=>{
    console.log(a,b);
    if( a === 0 || b === 0){
      return 0;
    }
    if(isEven(b)){
      return multiply(multiplyByTwo(a),divideByTwo(b));
    }else if(isPositive(b)){
      return multiply(multiplyByTwo(a),divideByTwo(b-1))+a;
    }else{
      return multiply(multiplyByTwo(a),divideByTwo(b+1))-a;
    }
  };
  const multiplyUnsigned = (a,b)=>{
    let result = 0;
    let bitIndex = 0;
    let multiplier = b;
    while(multiplier!=0){
      if(multiplier & 1){
        result += (a << bitIndex);
      }
      bitIndex += 1 ;
      multiplier >>= 1;
    }
    return result;
  };
  const countSetBits = (num)=>{

    let count = 0;

    while(num!=0){
      if(num & 1){
        count+=1;
      }
      num >>>= 1;
    }
    return count;
  };
  const bitsDiff = (num1,num2)=>{
    return countSetBits(num1 ^ num2);
  };
  const bitLength = (num)=>{
    let bitCount = 0;
    while( num >= (1<<bitCount)){
      bitCount += 1;
    }
    return bitCount;
  };
  const isPowerOfTwo = (num)=>{
    return (num & (num - 1)) ? false : true; 
  };
  const fullAdder = (a,b)=>{

    let result = 0;
    let carry = 0;
  
    // js位运算 最高32位
    for (let i = 0; i < 32; i += 1) {
      const ai = getBit(a, i);
      const bi = getBit(b, i);
      const carryIn = carry;
  
      const aiPlusBi = ai ^ bi;
  
      const bitSum = aiPlusBi ^ carryIn;
  
      const carryOut = (aiPlusBi & carryIn) | (ai & bi);
      carry = carryOut;
  
      result |= bitSum << i;
    }
  
    return result;
  };


  window.BIT = {
    getBit,setBit,clearBit,updateBit,isEven,isPositive,multiplyByTwo,multiply,divideByTwo,multiplyUnsigned,countSetBits,bitsDiff,bitLength,isPowerOfTwo,fullAdder,switchSign
  }

})();

位运算