JavaScript: fast floor of numeric values using the tilde operator

OK, put this one in the completely weird bucket. It works, but damn it’s obscure.

photo © 2010 Fling Poo | more info (via: Wylio)The tilde operator (~) is one of those bitwise operators that can be useful, but that aren’t used in general JavaScript programming. Put baldly, it inverts the bits of a 32-bit value. Bitwise NOT in other words.

OK, a step back. JavaScript doesn’t have 32-bit values; its number type is an IEEE double floating point value. There is an internal ‘abstract’ routine that’s known as ToInt32. ECMAScript v5 (pdf) defines it in clause 9.5:

1. Let number be the result of calling ToNumber on the input argument.
2. If number is NaN, +0, -0, +8, or -8, return +0.
3. Let posInt be sign(number) * floor(abs(number)).
4. Let int32bit be posInt modulo 2³².
5. If int32bit is greater than or equal to 2³¹, return int32bit - 2³², otherwise return int32bit.

So, in essence it takes a floating point number value, calculates its floor as a 32-bit signed integer. There’s a big problem with it though: it’s internal and we can’t ever access it directly. It’s also ‘abstract’, which means it doesn’t exist per se, the interpreter/compiler is free to apply any old optimization it needs to. We can only use its behavior when we use some operator that works on 32-bit integers: JavaScript will make the conversion for us, do the operation on the 32-bit operator, and then convert the answer back to a number variable. The operators I’m talking about here are the bitwise operators: << (left shift), >> (right shift with sign extension), >>> (right shift with zero fill), & (bitwise AND), | (bitwise OR), ^ (bitwise XOR) and our new friend ~ (bitwise NOT).

The nice thing about bitwise NOT is that it’s unary and, if you apply it twice, you get the same 32-bit integer you started with. (I think you’re beginning to see where this is going…)

OK. let’s suppose we write a dice-throwing function. It’s got to return an integer between 1 and 6. A first cut might look like this:

var throwDie = function () {
  return Math.floor(Math.random() * 6) + 1;
};

Nice and obvious: Math.random() returns a value between 0.0 (inclusive) and 1.0 (exclusive), we multiply by 6 (0.0 <= value < 6.0), take the floor (integer, 0 <= value < 6), and add 1.

However, using our new knowledge we can write:

var throwDie = function () {
  return ~~(Math.random() * 6) + 1;
};

The first application of the tilde operator takes the floor for us and NOTs it (well, to be pedantic, it applies the abstract function above to get a floored 32-bit value and then NOTs that), so we apply the tilde operator again to undo the NOT. Double tilde stands in for Math.floor(), providing that we’re talking about numbers in the 32-bit signed integer range.

Less typing, but, boy, is it obscure!

  Loading links to posts on similar topics...

1 Response

#1 Chilla42o said...

28-Jul-11 5:06 AM

The tilde operator applied to arrays makes a fast and easy inArray-check:

Single tilde:

~['apple','banana','ananas'].indexOf('banana'); // = -2 (negative index starting with -1, 0 if not found)

~['apple','banana','ananas'].indexOf('orange'); // = 0 / not found

Double tilde:

~~['apple','banana','ananas'].indexOf('banana');  // = 1 (positive index starting with 0, -1 if not found)

~~['apple','banana','ananas'].indexOf('orange'); // = -1 / not found

Leave a response

Note: some MarkDown is allowed, but HTML is not. Expand to show what's available.

•  Emphasize with italics: surround word with underscores _emphasis_
•  Emphasize strongly: surround word with double-asterisks **strong**
•  Link: surround text with square brackets, url with parentheses [text](url)
•  Inline code: surround text with backticks `IEnumerable`
•  Unordered list: start each line with an asterisk, space * an item
•  Ordered list: start each line with a digit, period, space 1. an item
•  Insert code block: start each line with four spaces
•  Insert blockquote: start each line with right-angle-bracket, space > Now is the time...

Name (required) Mail (will not be published) (required) Website Response Submit

Preview of response