JavaScript Data Structures 

Contents

1. The Associative Array
2. The String Object
3. The Array object
4. Speed dating - the art of the JavaScript Date object
5. Doing JavaScript Date Calculations
6. A Time Interval Object
7. Collection Object
8. Stacks, Queue & Deque
9. The Linked List
10. A Lisp-like list
11. The Binary Tree
12. Bit manipulation
13. Typed Arrays I
14. Typed Arrays II
15. Master JavaScript Regular Expressions
    * First Draft

JavaScript is a high-level language that does its best to keep you away from low level considerations of the way that hardware works. However no matter how high-level the language is there are times when you have to remember that data is stored as bits and you have to find a way to work directly with those bits.

Bit manipulation in JavaScript is complicated by the way that it attempts to be completely type free. One of the consequences of this type free approach is that numbers are always stored as 64-bit floating point values - i.e. double precision floating point.

Yes - that's correct JavaScript doesn't have an integer type that you can make use of. When needed JavaScript will perform an internal conversion to a 32-bit value but you can't gain access directly to this integer and it is converted back to floating point format as soon as it is possible.

So JavaScript is different when it comes to bit manipulation but not that difficult. Let's see how it all works.

The bitwise operators

JavaScript has a number of operators designed to allow you to perform bit manipulation. There are four logical operators:

As you would expect the not operator has the highest priority.

Notice that there are also corresponding logical operators  &&, || and ! that only work with Boolean values and not bit patterns.

If you are more familiar with other languages you might well confuse ^ with raise to a power. 

The bitwise operators work with numeric data which is converted from floating point to a 32-bit integer, operated on and then converted back to floating point. As a floating double can store a 32-bit integer without loss of precision everything works transparently as long as you stay within the 32-bit limit.

For example:

var a = 0xF0;
var b = 0xFF;
var c = ~a & b;
alert(c);

works out Not(a)=0F and b i.e. 0F & FF which is F. You should see the result 15 in decimal displayed.

Notice that bit manipulation is usually easiest to try out using hexadecimal notation e.g. 0xF is 15 in decimal.

There is no way of entering binary directly in JavaScript but you can use hex and octal and there is the paresInt function which will convert from a range of bases.

So what happens if you go over the 32-bit limit?

In fact strange things start to happen before you reach the 32-bit limit because the 32-bit value is signed and this means that if the highest bit is one the returned value is negative.

For example:

var a = 0xFFFFFFF;
var b = 0xFFFFFFF
var c = a & b;
alert(c.toString(16));

displays 0xFFFFFFF which is what you would expect. Notice that toString(16) converts the floating point number to a hex string.

Now try adding one more F to both values i.e. a full 32-bit value all set to one. The result displays as -1 which might not be what you expect but it is perfectly correct.

The result of anding two full 32-bit values both set to one is a 32-bit value with all bits set to one but as the 32-bit value is interpreted as a signed value this converts to -1 (twos complement). 

You don't have to worry about this too much as the bit pattern corresponding to -1 is 32 bits all set to one so everything should carry on working is you use the value for further bit manipulation.

Now consider what happens if you add one more F to the values. In this case the values are 36 bits all set to one and the result should also be 36 bits all set to one - but no.

Both the a and b values are converted to 32-bit values the two values are anded together and the result is a 32-bit result i.e. -1 as before. 

Beyond 32 bits

So what happens if you try to work with bitwise operators on values that aren't representable as 32-bit integers?

To do this the JavaScript interpreter calls the internal ToInt32 function (you can't use this in your programs). This performs an "intelligent" conversion to a 32-bit integer.

It ignores all fractional parts by truncation.

If the value is larger than a 32-bit integer can store then the result is 32 bits all set to one i.e. -1 in twos complement.

If the value is a fraction smaller than one then the result is zero.

If the value is infinity (plus or minus) or NaN then the result is zero.

You will also be pleased to learn that true evaluates to one and false to zero so you can use the bitwise logical operators on Boolean values. Just about every other possible value returns 0.

The only real problems with JavaScript's bitwise operators are that they are restricted to 32 bits and they are not especially fast because of the need to do conversion from floating point double precision to 32-bit integer and then back again.