JavaScript Bit Manipulation
Written by Ian Elliot   
Thursday, 11 July 2019
Article Index
JavaScript Bit Manipulation
Masks
Shifts

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 left 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 left and so result contains 0xF0.

Similarly the >> operator shifts to the right 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.

One very common error is to test the value and mask computed within an if statement without taking account of operator priorities. For example:

if( value & mask === mask) …

seems as if it is testing to see if all of the bits specified by the mask are set. It isn’t. As the === has a higher priority than & what you are actually working out is:

if( value & (mask === mask))…

which isn’t quite what is required. The correct expression is:

if( (value & mask) === mask)…

or you could use

if( !(~value & mask))…

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.

 datastruct

Related Articles

Hexadecimal 

Reading A BMP File In JavaScript 

Binary - Negative Numbers 


JavaScript Data Structures 

Cover

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
 

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

 

raspberry pi books

 

Comments




or email your comment to: comments@i-programmer.info

<ASIN:1871962579>

<ASIN:1871962560>

<ASIN:0596517742>

<ASIN:0596806752>

 



Last Updated ( Saturday, 27 July 2019 )