weixin_39738774
weixin_39738774
2020-12-09 05:22

我们要不要在 JS 使用二进制位运算?

Javascript 完全套用了 Java 的位运算符,包括按位与&、按位或|、按位异或^、按位非~、左移<<、带符号的右移>>和用0补足的右移>>>
这套运算符针对的是整数,所以对 Javascript 完全无用,因为 Javascript 内部,所有数字都保存为双精度浮点数。如果使用它们的话,Javascript 不得不将运算数先转为整数,然后再进行运算,这样就降低了速度。而且"按位与运算符"&同"逻辑与运算符"&&,很容易混淆。

上面的一段文字来源于一篇比较老的博文http://www.ruanyifeng.com/blog/2010/01/12_javascript_syntax_structures_you_should_not_use.html。说的并没太错,但是却没有告诉我们到底会降低多少速度,“"按位与运算符"&同"逻辑与运算符"&&,很容易混淆”,真的容易混淆吗?(博主是自己很钦佩的一个前辈,自己接下来主要是想分享一些 JS 可能不常用的技巧(理解了以后就常用了:p))

到底会慢多少?

先拿一个位运算左移<<等效*2的例子,别吐槽这么去测试有什么意义,自己真的写代码的时候基本没人会去使用位移操作。来,打开 Console 看例子: http://lishengzxc.github.io/bblog/Bitwise-Shift.html

 javascript

  console.time('*2');
  for (var i = 0; i < 10000000; i++) {
    1.1 * 2
  }
  console.timeEnd('*2');

  console.time('<<1');
  for (var i = 0; i < 10000000; i++) {
    1.1 << 1
  }
  console.timeEnd('<<1');

  console.time('/4');
  for (var i = 0; i < 10000000; i++) {
    1.1 / 4
  }
  console.timeEnd('/4');

  console.time('>>2');
  for (var i = 0; i < 10000000; i++) {
    1.1 >> 2
  }
  console.timeEnd('>>2');

结果:我的浏览器是 Chrome,MBP15(13年),发现循环10000000次也仅相差不到 5ms。而且你发现多刷新一次,发现直接整数乘法或除法和左移右移谁快谁慢是不确定的,反正相差无几。


*2: 29.870ms
<<1: 33.389ms
/4: 33.003ms
>>2: 27.841ms

再来看一个取整的例子:http://lishengzxc.github.io/bblog/Bitwise-GetInt.html

这是一个Number的取整的例子,而不是StringNumber

 javascript
  console.time('| 0');
  for (var i = 0; i < 10000000; i++) {
    i / 3 | 0
  }
  console.timeEnd('| 0');

  console.time('Math.floor');
  for (var i = 0; i < 10000000; i++) {
    Math.floor(i / 3)
  }
  console.timeEnd('Math.floor');

  console.time('parseInt(x)');
  for (var i = 0; i < 10000000; i++) {
    parseInt(i / 3)
  }
  console.timeEnd('parseInt(x)');

  console.time('parseInt(x, 10)');
  for (var i = 0; i < 10000000; i++) {
    parseInt(i / 3, 10)
  }
  console.timeEnd('parseInt(x, 10)');

  console.time('(| 0) + 1');
  for (var i = 0; i < 10000000; i++) {
    (i / 3 | 0) + 1
  }
  console.timeEnd('(| 0) + 1');

  console.time('Math.ceil');
  for (var i = 0; i < 10000000; i++) {
    Math.ceil(i / 3)
  }
  console.timeEnd('Math.ceil');

结果:我们发现这个时候按位或|要快于其他 API,除了这点外,大家在注意下parseInt(),可以发现,不带第二个参数很重要,首先明确是了是十进制同时速度也快了不少。

 javascript
| 0: 55.003ms
Math.floor: 55.196ms
parseInt(x): 197.627ms
parseInt(x, 10): 131.175ms
(| 0) + 1: 28.960ms
Math.ceil: 113.976ms

不过,虽然按位或|Number的取整加速不少,但是它只适用于NumberString还是老老实实的吧,比如:

 javascript
Math.ceil('1234.23'); //1235
parseInt('1234,23', 10); //1234

JS 使用二进制位运算的一些例子

我举得例子肯定不全,欢迎大家头脑风暴~

| 运算符 | 用法 | 描述 | | --- | --- | --- | | 按位与(AND) | a & b | 对于每一个比特位,只有两个操作数相应的比特位都是1时,结果才为1,否则为0。 | | 按位或(OR) | a \| b | 对于每一个比特位,当两个操作数相应的比特位至少有一个1时,结果为1,否则为0。 | | 按位异或(XOR) | a ^ b | 对于每一个比特位,当两个操作数相应的比特位有且只有一个1时,结果为1,否则为0。 | | 按位非(NOT) | ~ a | 反转操作数的比特位,即0变成1,1变成0。 | | 左移(Left shift) | a << b | 将 a 的二进制形式向左移 b (< 32) 比特位,右边用0填充。 | | 有符号右移 | a >> b | 将 a 的二进制表示向右移 b (< 32) 位,丢弃被移出的位。 | | 无符号右移 | a >>> b | 将 a 的二进制表示向右移 b (< 32) 位,丢弃被移出的位,并使用 0 在左侧填充。 |

随机获取数组某项

随机获取某项关键是随机拿到满足数组长度的索引

 javascript
var arr = [...];
var len = arr.length;

// 一般方法:
var rIndex = Math.floor((Math.random() * len))

// 使用位运算的方法
var rIndex = Math.random() * len | 0

是不是简洁了许多?

indexOf()返回trueorfalse

 javascript
var arr = [...];

// 一般方法:
var isExist = function(array, value) {
    return array.indexOf(value) > 0;
}

// 使用位运算的方法:将 -1 转变为 false
var isExist = function(array, value) {
    return !!~array.indexOf(value);
}

补充:ES6/7 和indexOf()类似的 API

 javascript
// .find()
[1, 5, 10, 15].find(function(value, index, arr) {
  return value > 9;
}) // 10,未找到的话,返回 undefined

// .findIndex()
[1, 5, 10, 15].findIndex(function(value, index, arr) {
  return value > 9;
}) // 2,未找到的话,返回 -1

// .includes()
[1, 2, 3].includes(2);     // true
[1, 2, 3].includes(4);     // false
[1, 2, NaN].includes(NaN); // true

切换变量 0 或 1

 javascript
// 一般方法:
if (toggle) {
    toggle = 0;
} else {
    toggle = 1;
}

// 一般方法的简写:
togle = toggle ? 0 : 1;

// 使用位运算的方法:
toggle ^= 1;

碰撞检测优化(标示我需不要和你检测碰撞)

如果已经对 A 测试了 B,就没有必要再对 B 测试 A。我们需要维护一个二维数组保存每个碰撞对象的2个标志impactFlagimpactFlags

| | Bullet | Tank | Wall | | --- | --- | --- | --- | | impactFlag | 1 | 2 | 4 | | impactFlags | 2+4 | 0 | 0 |

 javascript
doCheckImpact = obj1.impactFlag & obj2.impactFlags // 非0标示需要进行碰撞检测(0 == false)

其实 *inux 的权限系统 7 = 1 + 2 + 4 也是这么设计的。


7 = 111

1 = 001
2 = 010
4 = 100

将权限值和 1、2、4 按位与&,就能得出目标用户对目标文件有什么权限了。

left-pad

https://www.npmjs.com/package/left-pad

最新的 left-pad,因为 PR 源码已经更改了。

 javascript
// 以前的版本
function leftpad (str, len, ch) {
  str = String(str);

  var i = -1;

  if (!ch && ch !== 0) ch = " ";

  len = len - str.length;

  while (++i < len) {
    str = ch + str;
  }

  return str;
}

以前的版本中,补 n 位字符,字符串链接时间复杂度是 O(n) 的,字符串需要执行 n 次的链接操作,那可以降低时间复杂度吗?

 javascript
// 左耳朵耗子的 PR
function leftpad (str, len, ch) {
  //convert the `str` to String
  str = str +''; 

  //needn't to pad
  len = len - str.length;
  if (len <= 0) return str;

  //convert the `ch` to String
  if (!ch && ch !== 0) ch = ' ';
  ch = ch + ''; 

  var pad = '';
  while (true) {
    if (len & 1) pad += ch;
    len >>= 1;
    if (len) ch += ch;
    else break;
  }
  return pad + str;
}

这里用了2个位运算,&>>,其实算法的逻辑就是去算需要填充多少位。
len和 1 去按位与是为了看右移后的len是奇数还是偶数,比如:

 javascript
2 & 1 //0
3 & 1 //1
4 & 1 //0
5 & 1 //1

根据len的奇偶觉得填充字符串要不要补上一个。

循环中的len,每次右移动后,判断剩下的len,还能继续右移吗,如果可以,就将填充字符串pad倍增ch+=ch(字符串倍增)。

这样的逻辑是的left-pad更加高效了。

 javascript
// 月影大神的
function leftpad(str, len, ch){
  str = "" + str;
  if(!ch && ch !== 0) ch = " ";
  ch = "" + ch;

  var padlen = len - str.length;
  if(padlen <= 0) return str;

  var padch = padlen & 1 ? ch : "";

  while(padlen >>= 1){
    ch += ch;
    if(padlen & 1){
        padch += ch;
    }
  }
  return padch + str;
}

无法理解的同学,可以单步调试下

left-pad-debugger

补充 ES6/7 相关字符串拓展

.repeat()

repeat方法返回一个新字符串,表示将原字符串重复n次。

 javascript
'x'.repeat(3) // "xxx"
'hello'.repeat(2) // "hellohello"
'na'.repeat(0) // ""

.padStart(),.padEnd()

ES7推出了字符串补全长度的功能。如果某个字符串不够指定长度,会在头部或尾部补全。padStart用于头部补全,padEnd用于尾部补全。

 javascript
'x'.padStart(5, 'ab') // 'ababx'
'x'.padStart(4, 'ab') // 'abax'

'x'.padEnd(5, 'ab') // 'xabab'
'x'.padEnd(4, 'ab') // 'xaba'

最后

我们没要必要排斥在 JS 中使用位运算,欢迎大家补充更多的使用实例。

该提问来源于开源项目:lishengzxc/bblog

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

6条回答

  • weixin_39858124 weixin_39858124 5月前

    常用的~~ 16 05 10 2229_1 array = [myVar]; // to array

    点赞 评论 复制链接分享
  • weixin_39598584 weixin_39598584 5月前

    http://www.basecss.net/2014/03/27/code-learning/ by

    点赞 评论 复制链接分享
  • weixin_39657521 weixin_39657521 5月前

    *2: 41.327ms <<1: 28.248ms 我的是chrome 50,结果是这样,多次执行偶有移位比直接乘慢的情况

    点赞 评论 复制链接分享
  • weixin_39738774 weixin_39738774 5月前

    嗯,确实有,其实我觉得对于简单本身可以用直接运算的比必要用位运算,但是我们没有必要排斥它。

    点赞 评论 复制链接分享
  • weixin_39863161 weixin_39863161 5月前

    习惯用 ~~ 取整

    点赞 评论 复制链接分享
  • weixin_39738774 weixin_39738774 5月前

    恩 两次按位非 负负得正

    点赞 评论 复制链接分享