Tuesday, June 19, 2012

A deep dive into the Javascript NOT bitwise operator

I recently came across this example of the JavaScript NOT bitwise operator (achieved by using the ~ symbol).

var a = 9;
var b = ~a; // b is now -10

Essentially, when you precede a number with ~, you add 1 to original number and negate it:
so,
var b = ~a;
is the same as,
var b =  -(a + 1);

I got curious as to where this will be useful but more so why ~ results in the above formula.

The Question:
So why does applying ~ result in the -(original number + 1) formula being used.

My curiosity led me into the dark shadows of the highly confusing (for me anyway, always been my weak point) conversion and handling of binary data and "signed and unsigned" systems for storing and working with binary data.

Below is the summary of my findings which eventually answers the above question.

Step 1: bits and bytes
In JavaScript when we use the NOT bitwise operator we deal with a "32 bit signed system" to store and work with binary data (binary data is made up of 1 and 0 "bits"), essentially we use 4 "bytes" (8 bits = 1 byte) to store all the characters a user can enter using a keyboard (numbers, letters, symbols etc.)

So each character is stored in this complete binary pattern (notice it's four blocks of eight bits):
00000000 00000000 00000000 00000000

The lowest binary pattern is:
00000000 00000000 00000000 00000000
(which is the value 0)

and the highest binary pattern is:
11111111 11111111 11111111 11111111
(which is the value 4294967295)

> See how to convert binary into number values and vice versa by watching this short video.

Step 2: Signed and Unsigned
So in total a 32 bit system can store a total of 4294967296 different values (0 to 4294967295)

But this max 4294967296 limit is for a "32 bit unsigned system" system (where there is no such thing as positive and negative values but only positive values) so in other words 4294967296 positive values can be stored.

So the range for a 32 bit unsigned system is 0 to 4294967295

In a "32 bit signed system" the max limit needs to be shared by positive and negative values, so that would be:
-2147483648 up to 0 and then 0 up to 2147483647

So the range for a 32 bit signed system is -2147483648 to 2147483647

Step 3: It Now all Comes Together
Now, let's look at that number 9 again, in a "32 bit system" binary that's
0000000 00000000 00000000 00001001

Let's look at the example again:
var a = 9;
var b = ~a; // b comes -10

1) The first thing the ~ operator does is convert the number into a 32-bit number
So 9 becomes 0000000 00000000 00000000 00001001

2) Next it inverts (one’s complement) the entire binary pattern
So it now becomes 1111111 11111111 11111111 11110110

4) Finally, it turns it back into a number
Which is -10

But wait! If we convert 1111111 11111111 11111111 11110110 back into a number, based on the system shown in the video to convert binary back it should work out to be
4294967286, right?

True, but thats only in the case of a "unsigned" system, remember when using the ~ we start to deal a "signed" system. So the maximum positive value in a "32 bit signed system" is 2147483647 and what will happen is our value of 4294967286 has exceeded that limit and gone into the negative range. To work out the overflow into the negative numbers what we need to do is basically **substrate the total available values from a 32 bit system (4294967296) from our number (4294967286) that's too large and you get the overflow into negative, like so:

4294967286 - 4294967296
Which gives us -10

This -10 value is "theoretically" the same as 4294967286 but its just in signed and unsigned representation.

** This last bit is a bit confusing even to me, but its is easier to digest when looking at smaller numbers. lets say our limit is 15 (-8 to 7) and our number was 12

The signed representation will be
12-15 = -3

Conclusion:
I'm just a very curious guy who need to break down things down and see how things work, this is my understanding of this topic and I could have got a few things wrong. You really don't need to go into this kind of dept to look at the uses for the NOT bitwise operator. Here are some uses for it:

1) Using a double ~~ to get the same result as Math.floor or Math.ceil for numbers:

2) Using each bit in a bit system as individual "flags" as input to some system

* Let's say you need to send this set of params to a flash object or maybe for use in a canvas element
param1=true&param2=false&param3=true&param4=true&param5=false

* You could drop the param names and send them as just a comman seperated string
true,false,true,true,false

* Or you can go further and send them as 1's or 0s
10110

You now technically have a binary pattern and you can use Javascript bitwise operators now to manipulate the individual bits, for example, you can flip this entire param list by simple using ~

* Or you can even optimize this even further by converting the 10110 into its decimal representation of 22.

So we have converted
param1=true&param2=false&param3=true&param4=true&param5=false
into
22

Pretty cool huh?

References: 