A note on bit-wise operations

Today I read some JavaScript source code and stumbled on a line like var delta = ~~time; and I was unsure what that purpose of using ~~ was.

So I started to research and digging a bit deeper. It turns out that the binary not operator (~) when applied twice on a floating number (e.g. 4.12) returns an integer (~~4.12 = 4).

Why not simply use Math.floor(4.12)? It turns out that the bit-wise not operator applied twice is quite a bit faster than using the Math.floor method (see Link).

Let’s wind back a little bit and dig deeper into the workings here, because I’m sure you might be confused by how this works and what this actually does.

The ~ Operator

First of all, the binary not operator (~) basically switches all 1s to 0s and vice versa. Thus, if you have a binary representation of 0111011001 and apply ~ to it, it will be 1000100110.

I got a bit more interested in the exact workings, because it turned out, that ~4 = -5 and ~6 = -7, so a positive number becomes its negative number minus one. Why is this and why does it make sense?

Let’s start with a binary representation of 5: 0101

~5 = 1010

So in this case, 1010 is supposed to be a representation of -6?

Let’s think about this. So we have 4 bits in the case above, i.e. 4 positions of 0s or 1s. $2^4$ possibilities to encode with 4 bits, which is 16 different encodings (0000, 0001, 0010, 0011, 0100, 0101, ..., 1111).

Number representation in bits

When we want to represent positive and negative numbers using these 4 bits, we have to split these by 2, so we have 8 possibilities for positive numbers and 8 possibilities for negative numbers. But we also have the 0, so we either need to have one less positive or negative number (usually one less positive).

Alright, let’s build our construct and take the first 8 possibilities for 0 (0000) and the positive numbers 1 (0001) through 7 (0111).

Now the question is how to represent the negative ones.

Option 1: Negative Flag

One “natural” option would be to just use the highest bit to switch between positive and negative numbers like a flag. Thus, 1001 -> -1, 1010 -> -2 and so forth. But then, what is 1000? Is it another representation of 0? And is 1000 == 0000 ??? Seems ugly, right?

Another problem here is the mathematical operations. Let’s add some numbers in this representation, say add 1 and -1:

0001 + 1001 = 1010

-1 + 1 = -2 ? Not so great, right? Thus, in this represenation we would have to differentiate between positive and negative numbers when doing mathematical operations. Bummer.

Option 2: Two’s Complement

Typically, in modern architectures what is thus used is called two’s complement.

It is the natural evolution to have most mathematical operations in a consistent style.

How? Well, just like using the bits so far, we simply have the highest bit represent a negative value like this:

Let $b_3, b_2, b_1, b_0$ be our bit values, then our number simply is:

$num_{10} = -1 * b_3 * 2^3 + b_2 * 2^2 + b_1 * 2^1 + b_0 * 2^0$

$1001 = -1 * 2^3 + 2^0 = -8 + 1 = -7$

0001 + 1001 = 1010

$1010 = -1 * 2^3 + 2^1$ = -8 + 2 = -6.

So 1 + (-7) = -6 Hooray!

One side effect of the two’s complement representation is that x * -1 = ~x + 1 which is ~x = -x - 1 or in binary:

0001 * -1 = ~0001 + 0001 = 1110 + 0001 = 1111 =

$-1 * 2^3 + 2^2 + 2^1 + 2^0$ = -8 + 4 + 2 + 1 = -1

Intermediate summary

Phew, that was quite a bit of work, but so far you learned:

• Computers represent integer numbers in the two’s complement representation to have a single value for 0 and convenient ways to perform mathematical operations without having special rules for negative numbers.
• The ~ operator on an integer number converts the number from a positive one to a negative one which is one lower than the initial number (~5 = -6).
• When you want to get the negative number of a positive one you can thus use ~ and add one (-5 = ~5 + 1)
• Using ~~ on a float cuts off the floating part and returns the integer (~~-3.42 = -3, ~~5.23 = 5) and can be faster than Math.floor()

About that last part - what is the representation of a float and how does that ~~ part work. In fact, it was hard to get much information on this, but it turns out that the way this works is that the bitwise operators convert the float to an int before doing the bitwise flip, thus ~~5.23 = ~~5 = ~-6 = 5.

More exactly: numbers in JavaScript are stored as 64 bits floating point numbers, but the bitwise operations are performed on 32 bits signed integers, so a conversion occurs before and after the bitwise operation.

The performance part thus seems more related to the overhead the function call is providing.

Be aware though, that for negative numbers ~~-3.42 = -3 != Math.floor(-3.42) = -4

So, when handling positive numbers, you can use ~~ instead of Math.floor to gain some performance.

The same holds in PHP: ~~ is faster than floor() by a matter of about 200%. However, ~~ is as fast as is a cast to int: (int)

Summary

Today, we learned that:

• ~ is the bitwise not operator which flips all 0s to 1s and vice versa.
• Signed numbers are represented with the two’s complement which yields ~5 = -6
• ~~ is a performance trick to truncate a floating point number to an integer.
• ~~ is like Math.floor() for positive numbers, but not for negative ones as ~~-5.93 = -5 while Math.floor(-5.93) = -6

BONUS: All bitwise operators in JavaScript

• x << y: Returns x with the bits shifted to the left by y places (new bits on the right-hand-side are zeros). This is the same as multiplying x by Math.pow(2, y).
• x >> y: Returns x with the bits shifted to the right by y places. This is the same as dividing x by Math.pow(2, y).
• x & y: Does a “bitwise and”. Each bit of the output is 1 if the corresponding bit of x AND of y is 1, otherwise it’s 0.
• x | y: Does a “bitwise or”. Each bit of the output is 0 if the corresponding bit of x AND of y is 0, otherwise it’s 1.
• ~ x: Returns the complement of x - the number you get by switching each 1 for a 0 and each 0 for a 1. This is the same as -x - 1 as explained above.
• x ^ y: Does a “bitwise exclusive or”. Each bit of the output is the same as the corresponding bit in x if that bit is 0 in y, and it’s the complement of the bit in x if that bit is 1 in y.