Black lives matter

(Ad, please don’t block)

JavaScript only has floating point numbers. This post explains how integer operations are handled, specifically the bit shift operations. It will also answer the question whether `n >>> 0` is a good way of converting a number to a non-negative integer.

String.prototype.bin = function () { return parseInt(this, 2); }; Number.prototype.bin = function () { var sign = (this < 0 ? "-" : ""); var result = Math.abs(this).toString(2); while(result.length < 32) { result = "0" + result; } return sign + result; }The methods in use:

> "110".bin() 6 > 6..bin() '00000000000000000000000000000110'

- Integer: a value in the range [−2
^{53}, +2^{53}]. Used for: most integer arguments (indices, dates, etc.). Higher and lower integers can be represented, but only the integers in the interval are contiguous [1]. - Uint16: 16 bit unsigned integers in the range [0, 2
^{16}−1]. Used for: character codes. - Uint32: 32 bit unsigned integers in the range [0, 2
^{32}−1]. Used for: array lengths. - Int32: 32 bit signed integers in the range [−2
^{31}, 2^{31}−1]. Used for: bitwise not, binary bitwise operators, unsigned shift.

sign(Intuitively, one removes all decimals. The trick with sign and abs is necessary, because floor converts a floating point number to the nextn) ⋅ floor(abs(n))

> Math.floor(3.2) 3 > Math.floor(-3.2) -4Conversion to integer can be implemented without a sign function as follows:

function ToInteger(x) { x = Number(x); return x < 0 ? Math.ceil(x) : Math.floor(x); }We deviate from the normal practice of letting (non-constructor) functions start with a lowercase letter to conform with the names used by the ECMAScript 5.1 specification.

function modulo(a, b) { return a - Math.floor(a/b)*b; } function ToUint32(x) { return modulo(ToInteger(x), Math.pow(2, 32)); }The modulo operation becomes apparent at numbers close to integer multiples of 2

> ToUint32(Math.pow(2,32)) 0 > ToUint32(Math.pow(2,32)+1) 1 > ToUint32(-Math.pow(2,32)) 0 > ToUint32(-Math.pow(2,32)-1) 4294967295 > ToUint32(-1) 4294967295The result of converting a negative number makes more sense if we look at its binary representation. To negate a binary number, you invert each of its digits and then add one. The inversion is called the ones’ complement, adding one turns it into the twos’ complement. Illustrating the process with 4 digits:

0001 1 1110 ones’ complement of 1 1111 −1, twos’ complement of 1 10000 −1 + 1The last line explains why the twos’ complement really is a negative number if the digits are fixed: The result of adding 1 to 1111 is 0, ignoring the fifth digit.

> ToUint32(-1).bin() '11111111111111111111111111111111'

function ToInt32(x) { var uint32 = ToUint32(x); if (uint32 >= Math.pow(2, 31)) { return uint32 - Math.pow(2, 32) } else { return uint32; } }Results:

> ToInt32(-1) -1 > ToInt32(4294967295) -1

- Signed shift left
`<<` - Signed shift right
`>>` - Unsigned shift right
`>>>`

> -4 >> 1 -2 > 4 >> 1 2At a binary level, we see how the digits are shifted right while the highest digit stays the same.

> ("10000000000000000000000000000010".bin() >> 1).bin() '11000000000000000000000000000001'

> ("10000000000000000000000000000010".bin() >>> 1).bin() '01000000000000000000000000000001'The sign is not preserved, the result is always a Uint32:

> -4 >>> 1 2147483646

> 4 << 1 8 > -4 << 1 -8For left shifts, signed and unsigned operation are indistinguishable.

> ("10000000000000000000000000000010".bin() << 1).bin() '00000000000000000000000000000100'To see why, we again turn to 4 digit binary numbers and single-digit shifts. A signed left shift means that if the highest digit is 1 before the shift, it is also 1 after the shift. If there was a number where we could observe the difference between signed and unsigned left shifts, then its second-highest digit would have to be 0 (otherwise the highest digit would be 1 in either case). That is, it would have to look like this:

10__The result of an unsigned left shift is

Another way to look at it is that for negative numbers, the highest digit is 1. The lower the remaining digits are, the lower the number is. For example, the lowest 4-digit negative number is

1000 (−8, the twos’ complement of itself)Any number 10__ is -5 or lower (-5, -6, -7, -8). But multiplying either one of those numbers by 2 would put it out of range. Therefore, a signed shift makes no sense.

function ToUint32(x) { return x >>> 0; } function ToInt32(x) { return x >> 0; }

- Math.floor() converts its argument to the closest lower integer.
> Math.floor(3.8) 3 > Math.floor(-3.8) -4

- Math.ceil() converts its argument to the closest higher integer.
> Math.ceil(3.2) 4 > Math.ceil(-3.2) -3

- Math.round() converts its argument to the closest integer. Examples:
> Math.round(3.2) 3 > Math.round(3.5) 4 > Math.round(3.8) 4

The result of rounding -3.5 is slightly unexpected.> Math.round(-3.2) -3 > Math.round(-3.5) -3 > Math.round(-3.8) -4

Therefore,`Math.round(x)`is the same asMath.ceil(x + 0.5)

The modulo operations performed by `ToUint32` and `ToInt32` are rarely useful in practice. The following equivalent to ToUint32 is sometimes used to convert any `value` to a non-negative integer.

value >>> 0That is a lot of magic for a single expression! It is usually better to split that up into several statements or expressions. You might even want to throw an exception if a value is below 0 or not a number. That would also avoid some of the more unexpected results of the >>> operator:

> -1 >>> 0 4294967295