警惕位移运算<<的坑
发布于 6 年前 作者 zy445566 5855 次浏览 来自 分享

在一次代码优化的过程中把

// a,b都为正整数且大于0
while (a>=b) {
    a-=b;
}

优化为

// a,b都为正整数且大于0
while (a>=b) {
    let tmpB = b;
    while (a>=tmpB) {
        let tmpShiftB = tmpB<<1;
        if (a>=tmpShiftB) {
            tmpB = tmpShiftB;
        } else {
            a-=tmpB;
        }
    }
}

本意是如果a很大,b很小的情况,也能把快速进行减法运算。 但后来发现a一旦很大,就会死循环,这个还是概率出现。 后来debug发现到一定时候tmpShiftB会变成0,导致死循环。 当时就想肯定是位移符的坑,后来发现有下面问题

tmpShiftB到达2147483648后左移一位变0

我一看乐了,这不是2的32次方嘛,肯定是JS当有符号的int32型算了,然后溢出了,八成是谷歌引擎的的BUG! 但想想别高兴的太早,看看标准怎么说,毕竟制定标准的人也贼坑。让我们看看标准怎么写的。

ecma-262的第9版左位移说明

12.9.3The Left Shift Operator ( << )
NOTE
Performs a bitwise left shift operation on the left operand by the amount specified by the right operand.

12.9.3.1Runtime Semantics: Evaluation
ShiftExpression:ShiftExpression<<AdditiveExpression
Let lref be the result of evaluating ShiftExpression.
Let lval be ? GetValue(lref).
Let rref be the result of evaluating AdditiveExpression.
Let rval be ? GetValue(rref).
Let lnum be ? ToInt32(lval).
Let rnum be ? ToUint32(rval).
Let shiftCount be the result of masking out all but the least significant 5 bits of rnum, that is, compute rnum & 0x1F.
Return the result of left shifting lnum by shiftCount bits. The result is a signed 32-bit integer.

翻译下来大概意思是:

左表达式<<右表达式

左表达式结果转成Int32(有符号的int的32位类型),结果取名lnum

右表达式结果转成Uint32(无符号的int的32未类型),同时进行& 0x1F运算(即保留2进制的后5位,再白话一点就是保留32以内的位的数值,但和%32又有些不同),结果取名shiftCount

最后再把lnum左位移shiftCount位,并把这个结果再转换成有符号的int的32位类型

一看下来坏了,且不说左表达式结果转成了有符号的int的32位类型,位移后的结果也给转成了有符号的int的32位类型。果然是标准坑爹。

结论

看来以后使用左位移符都要小心了,只适用于int32的范围(-2^32~2^32),要是有可能超过,看来是断断不能用了。看来JS的世界精确整数也不一定就是(-2^53~2^53)范围了。

17 回复
function uint32ToBuffer(num) {
	let buffer = Buffer.alloc(4)
	buffer.writeInt32BE(num)
	return buffer
}

console.log(uint32ToBuffer(1073741824).toString('hex')) // 40000000
console.log(uint32ToBuffer(-2147483648).toString('hex')) // 80000000
  • 有符号32位整型1073741824,以二进制表示为0100 0000 0000 0000 0000 0000 0000 0000
  • 向左位移一位为1000 0000 0000 0000 0000 0000 0000 0000
  • 在有符号32位整形中,由于第一位为1,表示负数,转成十进制就是-2147483648

这不是计算机基础吗?哪里有Bug?哪里坑?

@CoderIvan 你没看全,我说的是JS运算符普遍是支持(-2^53~2^53),而位移符只支持(-2^32~2^32),所以坑 比如

2147483648*2;  //达到期望4294967296
2147483648+2147483648; //达到期望4294967296
2147483648<<1; //结果0,未达到期望4294967296

@zy445566

Number类型统一按浮点数处理,64位存储,整数是按最大54位来算最大最小数的,否则会丧失精度;某些操作(如数组索引还有位操作)是按32位处理的~~

传送门

@CoderIvan 嗯,科普了,注意数组索引和位运算,但我觉得这样的标准很奇怪,一不小心就溢出了

不单单左移 js 里的位运算符都是按32位有符号整数来计算的, 以前处理IP地址的时候也碰到过这个坑

为什么Javascript要把Number转成32位有符号整形来进行位移,以下是我的分析:

  1. Javascript存储数值均使用Double类型,即64位浮点数
  2. 由于64位的浮点数的存储方式,最高的1位是符号位,接着的11位是指数,剩下的52位为有效数字。
  3. 由于2,所以使用移位运算符,不能在这个的基础上进行,因为明显会造成不可预计的错误。
  4. 所以需要将浮点数转成整数的存储方式进行操作
  5. 而64位的浮点数的最大可表示整数为2^52,向下取,只能转成有符号32位整数
  6. 然后进行位移操作

@CoderIvan 你说的其实就是 IEEE-754 对 64 位双精度浮点数的描述,js 的 number 就是采用的这个

普通业务代码应该禁用位移

话说

// a,b都为正整数且大于0
while (a>=b) {
    a-=b;
}

这个运算不就等于 a % b 吗?

@alsotang 比如这题

divide two integers without using multiplication, division and mod operator. //不能用乘法、除法和取模。

这哪儿是坑啊,2^53 的 MAX_SAFE_INTEGER 说的是浮点数,而位移运算需要转换为整数。随便一个教程都会讲到 https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Operators/Bitwise_Operators

按位操作符(Bitwise operators) 将其操作数(operands)当作32位的比特序列(由0和1组成),而不是十进制、十六进制或八进制数值。

所有的按位操作符的操作数都会被转成补码(two’s complement)形式的有符号32位整数。

某些语言更奇葩,运算结果依赖于平台,32 位平台按 uint32 算,64 位平台按 uint64 算,岂不是更坑。也有依赖于编译器的,如果 64 位电脑安装一个 32 位编译器,就按 uint 32 算了。

根据IEEE-754标准,64位浮点数的小数位是52位(因此能精确表示52位的整数),阶码11位,符号位1位。因此用这52位来位移,好像是很自然的事情,没想到不是这样的,学习了

所以就有了BigInt
image.png

@youth7 想到一块去了

@dislido 我这个场景还远远没达到用BigInt,主要还是没想到位移符号,只支持正整数范围。搞区块链估计要经常用BigInt🐶

回到顶部