在一次代码优化的过程中把
// 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! 但想想别高兴的太早,看看标准怎么说,毕竟制定标准的人也贼坑。让我们看看标准怎么写的。
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)范围了。
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
@CoderIvan 嗯,科普了,注意数组索引和位运算,但我觉得这样的标准很奇怪,一不小心就溢出了
不单单左移 js 里的位运算符都是按32位有符号整数来计算的, 以前处理IP地址的时候也碰到过这个坑
为什么Javascript要把Number转成32位有符号整形来进行位移,以下是我的分析:
- Javascript存储数值均使用Double类型,即64位浮点数
- 由于64位的浮点数的存储方式,最高的1位是符号位,接着的11位是指数,剩下的52位为有效数字。
- 由于2,所以使用移位运算符,不能在这个的基础上进行,因为明显会造成不可预计的错误。
- 所以需要将浮点数转成整数的存储方式进行操作
- 而64位的浮点数的最大可表示整数为2^52,向下取,只能转成有符号32位整数
- 然后进行位移操作
@CoderIvan 你说的其实就是 IEEE-754 对 64 位双精度浮点数的描述,js 的 number 就是采用的这个
普通业务代码应该禁用位移
@waitingsong 正解
话说
// a,b都为正整数且大于0
while (a>=b) {
a-=b;
}
这个运算不就等于 a % b
吗?
这哪儿是坑啊,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
@youth7 想到一块去了
@dislido 我这个场景还远远没达到用BigInt,主要还是没想到位移符号,只支持正整数范围。搞区块链估计要经常用BigInt🐶
@zy445566 这么想也挺合理的。可以看看我这篇 https://cnodejs.org/topic/564a1ae51ba2ef107f854cfc