What sorts of things do you use masking operations for?

Often a low level API will require that particular bits in a status work are set or unset to make it operate in a particular way. However this is unusual in JavaScript because it generally doesn't access lower level APIs. However new developments like Canvas, WebGL and so on are changing this.

One of the best known uses of bit manipulation however predates HTML5 - exctracting the color codes from an RGB color value.

For example:

var RGBcolor=0x010203; var B=RGBcolor & 0x0000FF; var G=RGBcolor & 0x00FF00; var R=RGBcolor & 0xFF0000;

This takes an RGB value and splits it up into its components using appropriate masks.

The result is that you end up with 0x010000 stored in R, 0x000200 in G and 0x000003 in B. Notice that the value of B is correct but R and G are incorrect - the bits need shifting to the right.

This brings us to the use of the shift operators.

Shifting values

As well as the basic logical operators JavaScript also provides three shift operators which move the pattern of bits to the left or the right.

The << operator shifts the pattern of bits to the right shifting in zero into the low order.

So for example:

var data=0x0F; var result=data << 4;

shifts the bit pattern in data four places to the right and so result contains 0xF0.

Similarly the >> operator shifts to the left and shifts in a bit that is the same as the old top most bit into the high order bit. F

For example,

var data=0x0F; var result=data >>3;

shifts the bit pattern in data three places to the right and so result contains one i.e. 1111 -> 0001.

Notice that shifting one place to the left is the same as multiplying the value by two and shifting one place to the right is the same as integer division by 2.

For example:

var data=1; var result=data <<1;

stores two in result and

var data=8; var result=data >>1;

stores four in result.

What this means is that you can use either right and left shifts or multiplication and division by two to do the same job. Usually the shift operators are to be preferred because they are faster but this isn't as clear cut with JavaScript because of the converting from floating point to integer.

There is another problem with using multiplication and division as replacements for shift in JavaScript. Division doesn't convert to 32-bit integers and so the results can be different. For example 1>>1 is zero but 1/2 is 0.5. There are other problems when it comes to negative numbers but more of this later.

There is one more shift operator >>> this is an unsigned right shift operator and it is the same as the >> operator but it always shifts in a zero to the high order bit. For positive 32-bit integers the effect of >>> and >> is the same because in this case the initial topmost bit is zero and so both shift in a zero.

However they behave very differently on negative values. For example:

var data=-1; var result=data >>1;

stores -1 in result. The reason is that the initial bit pattern is all ones i.e. 32 bits all set to one and so shifting one place to the right shifts in another one as the high bit.

Compare this to

var data=-1; var result=data >>>1;

In this case a zero is shifted into the high bit and the value stored in result gives zero followed by 31 ones which is a positive value equal to 2147483647.

Which sort of shift should you use?

The answer is that it depends on what you are trying to do. If you are simply shifting bit patterns then using >>> is usually what you need because you don't want to treat the value as signed. If you are treating the number as signed then you need to use >>.

That is shifting using >> preserves the sign of the value whereas >>> doesn't.

For example:

var data=-200; var result=data >>1;

stores -100 in data but

var data=-200; var result=data >>>1;

stores 2147483548 in result.

Notice that >> gives the result that you get if you use division but >>> doesn't.

For this reason >> is usually called an arithmetic shift right and >> is called a logical shift right.

For example consider the problem of separating out the RGB values given earlier:

var RGBcolor=0x010203; var B=RGBcolor & 0x0000FF; var G=RGBcolor & 0x00FF00; var R=RGBcolor & 0xFF0000;

to shift the bits into the correct locations you would use:

var RGBcolor=0x010203; var B=RGBcolor & 0x0000FF; var G=RGBcolor & 0x00FF00; var R=RGBcolor & 0xFF0000; G=G >>> 8; R=R>>>16;

and now R is one, G is two and B is three as required.

Of course this isn't a good way to write the code because of the repeated conversion to 32-bit integers. Much better is:

var RGBcolor=0x010203; var B=RGBcolor & 0x0000FF; var G=(RGBcolor & 0x00FF00) >>> 8; var R=(RGBcolor & 0xFF0000) >>>16;

Also notice that you can write <<=, >>- and >>>= to shift the value of a variable "in place". For example:

value>>=9;

shifts the bit pattern in value 9 places to the right and stores the result in value i.e. it shifts value 9 places to the right.

Testing a bit

One common requirement is to test is a particular bit is set or unset.

Actually it is just as easy to test for any number of bits set or unset because the job is done using a mask.

As before if you create a mask with bits set corresponding to the bits you want to test then

value & mask

returns zero if and only if all of the bits the mask specifies are zero.

Similarly

~ value & mask

returns zero if and only if all of the bits the mask specifies are one.

Usually you only want to test for a single bit. For example:

var value=0x1F; var mask=0x10; var result=~value & mask;

the mask tests the fifth bit in the value which is a one and so result is zero. If you test for the fifth bit to be a zero using

var value=0x1F; var mask=0x10; var result=value & mask;

then the result is non-zero, 16 to be precise.

If you want to convert the test results to Boolean values you can use the logical operator !. For example:

!(~value & mask)

is true if and only if all of the bits in value specified by the mask are one and false otherwise.

Similarly

!(value & mask)

is true if and only if all of the bits in the value specified by the mask are zero and false otherwise.

In this form you can use the bit tests directly in an if statement without having to worry about using falsey and truthy values or testing for equality to zero.

Conclusion

So what is left to do?

At this point you can do just about any bit manipulations that you can do in other languages but only if you can fit the work into 32-bit integers.

The challenge is what to do if you need to work with 64-bit or bigger integers.

The solution is to write routines that split the 64-bit values up into multiple 32-bit values and carry out the operations separately - easier said than done!

Fortunately for most of the time 32 bits is enough.

jQuery - you can't help hearing about it, but it can seem a bit mysterious. jQuery experts seem to just write compact impenetrable code and even seeing what it is supposed to be doing can be tough. Th [ ... ]

Stacks, queues and deques are the most basic of the slightly more advanced data structures you will meet. The good news is that they are very, very easy to implement in JavaScript.