警惕位移运算<<的坑

发布于 7 年前作者 zy445566 6886 次预览最后一次回复是 7 年前来自分享

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

// 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 回复

CoderIvan

1楼•7 年前

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？哪里坑？

zy445566

2楼•7 年前

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

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

CoderIvan

3楼•7 年前

@zy445566

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

传送门

zy445566

4楼•7 年前

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

cnwhy

5楼•7 年前

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

CoderIvan

6楼•7 年前

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

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

hyj1991

7楼•7 年前

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

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

@waitingsong 正解

话说

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

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

zy445566

11楼•7 年前

@alsotang 比如这题

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

justjavac

12楼•7 年前

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