How To Truncate Numbers

裁掉小数部分的正确姿势

Wednesday, September 2, 2015

前段时间在开发抽奖游戏,需要生成一个随机数。游戏的规则之一是范围在 [1, 5] 的随机数是肯定不中奖的数字,对应的核心实现就是生成一个范围在 [1, 5] 的随机数。这是一个非常简单的实现,我也很果断地写下了这段代码:

return Math.random() * 5 + 1;

然而这个接口返回的不是整数,不符合要求,所以被改成了这样:

return Math.ceil(Math.random() * 5 + 1);

于是悲剧就这样发生了 ~~

本来这个接口生成的随机数是范围 [1, 6) 的任意小数,而预期的是范围 [1, 5] 的任意整数,结果由于 Math.ceil(),实际输出的是范围 [1, 6] 的整数,其中整数 6 却是一个可能中奖的数字。最终,结局就是 ~~~~

Math.ceil(x) v.s. Math.floor(x) v.s. Math.round(x)

The Math.ceil() function returns the smallest integer greater than or equal to a given number. The Math.floor() function returns the largest integer less than or equal to a given number.

Math.ceil() 方法对于小数的取舍策略是向上取整,而 Math.floor() 则是向下取整,相当于去掉小数部分。例如,对于 Math.random() * 5 + 1 生成的一个随机数 5.650360632222146,使用 Math.ceil() 方法所得到的结果是 6,而 Math.floor() 方法所得到的结果是 5。显然后者的结果才是符合范围 [1, 5] 的要求。Mozilla Developer Network 给出了一个标准的生成一定范围内的随机整数的代码示例

// Returns a random integer between min (included) and max (included)
// Using Math.round() will give you a non-uniform distribution!
function getRandomIntInclusive(min, max) {
  return Math.floor(
    Math.random() * (max - min + 1)
  ) + min;
}

在注释里提到了 Math.round() 方法。该方法就是用四舍五入对小数进行取舍。Mozilla Developer Network 的描述如下:

If the fractional portion of number is 0.5 or greater, the argument is rounded to the next higher integer. If the fractional portion of number is less than 0.5, the argument is rounded to the next lower integer.

如果 number 的小数部分是 .5 或者更大,输入的参数被四舍五入到下一个的更大的整数。 如果 number 的小数部分小于 .5,输入参数被四舍五入到下一个更小的整数。

所以,正如注释所说,在生成一定范围内的随机整数,如果使用 Math.round() 会产生一个非均匀分布的随机数

parseInt(string, radix)

其实也可以直接使用 parseInt 函数来舍去小数部分。按照 ECMAScript Language Specification 对该函数的描述

parseInt may interpret only a leading portion of string as an integer value; it ignores any characters that cannot be interpreted as part of the notation of an integer, and no indication is given that any such characters were ignored.

parseInt 函数可以只把 string 的开头部分解释为整数值;它会忽略所有不能解释为整数的字符,对于这些被忽略的字符,不会给出任何提示。

因此 parseInt 函数会忽视非整型数字的字符且遇到这样的字符就会停止解析。按道理可以利用这个特性来移除数字的小数部分,实现形似 Math.floor() 方法的效果。不过这仅仅只是个人猜测,我还是搜了一下 V8 对 parseInt 方法的实现:

// ECMA-262 - 15.1.2.2
function GlobalParseInt(string, radix) {
  if (IS_UNDEFINED(radix) || radix === 10 || radix === 0) {

    // Some people use parseInt instead of Math.floor.  This
    // optimization makes parseInt on a Smi 12 times faster (60ns    
    // vs 800ns).  The following optimization makes parseInt on a
    // non-Smi number 9 times faster (230ns vs 2070ns).  Together
    // they make parseInt on a string 1.4% slower (274ns vs 270ns).
    
    if (%_IsSmi(string)) return string;
    if (IS_NUMBER(string) &&
        ((0.01 < string && string < 1e9) ||
            (-1e9 < string && string < -0.01))) {
      // Truncate number.
      return string | 0;
    }
    string = TO_STRING_INLINE(string);
    radix = radix | 0;
  }
}

Smi: Smi represents integer Numbers that can be stored in 31 bits.

按照注释,确实存在使用 parseInt 来代替 Math.floor() 的做法。另外,V8 还为此做了性能优化(可惜结果牺牲了解释字符串的性能,哈哈 ~~ )从这段注释也说明了,使用 parseInt 函数的效果与 Math.floor() 一致

进一步阅读 V8 对 parseInt 函数的实现代码,可以看到,移除小数点部分的实现方法是位逻辑运算。这里的 parseInt 函数使用了或运算(return string | 0)来去除小数部分。

位逻辑运算

位逻辑运算是位运算的一种。至于位运算,它是一种非常底层的运算,直接处理每一个比特位,速度快但不直观。我们知道,JavaScript 的数值都是以 64 位浮点数的形式进行存储的,但是位运算只作用于 32 位整数,所以,当进行位运算时,JavaScript 会把数值自动转换成带符号的 32 位整数进行运算,结果相当于丢弃小数部分,返回整数部分(这个整数是带有符号的 32 位整数)。因此我们可以利用这样的特性来实现类似 Math.ceil() 和 Math.floor() 方法。

或运算符 OR

或运算的符号为 |,其真值表如下:

a b a OR b
1 0 1
1 1 1
0 0 0
0 1 1

按照或运算的规则,当一个数与 0 进行或运算,那么结果就相当于剔除小数部分,整数部分不变。例如,对于小数 6.1923 进行位运算,首先会舍去小数部分,而整数部分 6 的二进制表示为 110,接着与 0 进行或运算,其结果依然为 110,对应的十进制表示就是 6。不管对于正数还是负数,使用或运算来保留整数部分、移除小数部分都是有效的。

否运算 NOT

否运算的符号为 ~,其真值表如下:

a NOT a
1 0
0 1

按照否运算的规则,一个数对自身进行连续两次否运算,其结果还是自身。所以我们可以利用这个规则以及位运算只作用于整数的特性,对一个小数进行连续两次否运算,就可以去除小数部分了。例如对 5.645 进行两次否运算 ~~(5.545) 其运算结果就是 5

异或运算 XOR

异或运算的符号为 ^,其真值表如下:

a b a XOR b
1 0 1
1 1 0
0 0 0
0 1 1

按照异或的运算规则,当一个数与 0 进行异或后,其结果与进行或运算的效果一样,都是相当于剔除小数部分,整数部分不变。

移位运算符

我们还可以运用移位运算符,因为它跟位逻辑运算符同为位运算符,遵循同样的特性,只是这次我们位移 0 个比特位。

JavaScript 的移位运算符有三种:左移运算,它的符号是 <<,表示把一个数的二进制形式向左边移动,尾部补 0;右移运算,它的符号是 >>,表示把一个数的二进制形式向右边移动,符号位保持不变,最左边补上二进制 0;无符号的右移运算符(Zero-fill Right Shift),它的符号是 >>>,表示把一个数的二进制位形式向右移动,同时符号位总是用二进制 0 填充,所以结果总是非负的,即使右移 0 个比特位,结果同样也是非负的。

不过我们只是想要去除小数位,但不想移动整数部分的二进制,所以这次我们就只是简单地利用了位运算的特性,直接对一个小数的整数部分移动 0 位,这样就可以去除小数部分,也保持了整数部分的值了。例如 5.454 << 0 === 56.454 >> 0 === 67.342 >>> 0 === 7

特别需要注意的是,对于移除小数部分,仅有左移运算符和右移运算符对正数和负数都是有效的,而无符号的右移运算符只对正数有效,对负数则是无效的,这是因为该运算是无符号运算,其结果是一个无符号的 32 位整型。举个例子,对于数 -1,在 JavaScript 的存储形式为 -1 的补码,即 11111111 11111111 11111111 11111111,进行 0 比特位的无符号右移运算后,最左边不再充当符号位而是普通的数值,因此,其十进制结果就是 2^32 - 1 = 4294967295

Math.trunc(x)

Math.trunc(x) 方法是 ECMAScript 6 新增的方法,用于获取一个数的整数部分。Mozilla Developer Network 给出的描述如下:

Unlike other three Math methods: Math.floor(), Math.ceil() and Math.round(), the way Math.trunc() works is very simple and straightforward, just truncate the dot and the digits behind it, no matter whether the argument is a positive number or a negative number.

不同于其他的三个 Math 方法:Math.floor(),Math.ceil() 和 Math.round();Math.trunc() 的执行逻辑非常简单,不管是正数还是负数,都只删除数字的小数点以及小数部分。

Mozilla Developer Network 给出了 Math.trunc() 方法的一个 polyfill 实现:

Math.trunc = Math.trunc || function(x) {
  return x < 0 ? Math.ceil(x) : Math.floor(x);
};

这里之所以要处理 x < 0 的情况是因为去掉负的小数部分的结果与去掉正的小数的结果相反:对正的小数而言,去掉小数点意味着缩小小数;对于负的小数而言,去掉小数点则意味着扩大小数。通过以下两张对数学运算符 floor() 与 ceil() 的描述可以明显看出:对负的小数使用 ceil(),对正的小数使用 floor(),保证去掉小数部分的同时,保持整数部分不变:

http://mathworld.wolfram.com/FloorFunction.html

Floor Function

http://mathworld.wolfram.com/CeilingFunction.html

Cell Function

另外一个问题来了:Math.trunc() 是不是与 parseInt 函数或者 Math.floor() 的实现逻辑一样的呢?对于这个问题,我们只能继续扒 V8 的源代码了。以下是 V8 对 Math.trunc() 的实现:

// ES6 draft 09-27-13, section 20.2.2.34.
function MathTrunc(x) {
  x = +x;
  if (x > 0) return %_MathFloor(x);
  if (x < 0) return -%_MathFloor(-x);
  // -0, 0 or NaN.
  return x;
}

似乎源码的实现与上述的 JavaScript polyfill 很像!

通过查阅 ECMAScript Language Specification ,可以找到对 Math.ceil() 方法的描述The value of Math.ceil(x) is the same as the value of -Math.floor(-x). Math.ceil(x) 的值与 -Math.floor(-x) 的值一致__,另外对 Math.floor() 方法的描述则有:The value of Math.floor(x) is the same as the value of -Math.ceil(-x). Math.floor(x) 的值与 -Math.ceil(-x) 的值一致。对应到源码的实现则分别为:

// ECMA 262 - 15.8.2.6
function MathCeil(x) {
  return -%_MathFloor(-x);
}

// ECMA 262 - 15.8.2.9
function MathFloorJS(x) {
  return %_MathFloor(+x);
}

到这里,也就清楚 Math.trunc() 的 JavaScript polyfill 实现与 V8 的实现其实如出一辙。

总结

对于从一定区间内随机抽取一个数,一般都会调用 Math.random() 方法,不过该方法总是返回一个小数,所以存在超过最大值(或者最小值)的可能,因此我们往往需要裁掉小数部分,只保留整数部分。处理的方法有三种:

  • 对正的小数使用 Math.floor() ,对负的小数使用 Math.ceil();
  • 使用 Math.trunc();
  • 使用”或运算“。

参考资料