## 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 232.
5. If int32bit is greater than or equal to 231, return int32bit - 232, 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!

Now playing:
Johnson, Holly - Beat the System
(from Atomic City)

#### 1 Response

##### #1Chilla42o 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)

``````

Double tilde:

``````~~['apple','banana','ananas'].indexOf('banana');  // = 1 (positive index starting with 0, -1 if 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...`