I was going through a book on Data Structures and Algorithm with JavaScript when I found this piece of codes.

I need someone to help me explain the logic behind the code here, also the logic behind the value of var i in each method.

1. var i = (this._front length) & (this._size - 1); //explain this in push()

2. var i = (this._front length - 1) & (this._size - 1); // explain this in pop()

3. var i = (((( this._front - 1 ) & ( size - 1) ) ^ size ) - size );// explain this in unshift()

4. Please explain the general logic for each method, I have an issue with the use of & operator in the above statements, please why the use of & instead of %

var CircularDequeue = (()=> {
    class CircularDequeue {
        constructor() {
            // pseudo realistic 2^x value
            this._size = 1024;
            this._length = 0;
            this._front = 0;
            this._data = [];
        }

        push (item) {
            // get the length of the array
            var length = this._length;

            // calculate the end
            var i = (this._front   length) & (this._size - 1);

            // assign value to the current end of the data
            this._data[i] = item;

            // increment length for quick look up
            this._length = length   1;

            // return new length
            return this._length;
        }

        pop () {
            // get the length of the array
            var length = this._length;

            // calculate the end
            var i = (this._front   length - 1) & (this._size - 1);

            // copy the value to return
            var ret = this._data[i];

            // remove the value from data
            this._data[i] = undefined;

            // reduce length for look up
            this._length = length - 1;

            // return value
            return ret;
       }

       shift () {
            // get the current front of queue
            var front = this._front;

            // capture return value
            var ret = this._data[front];

            // reset value in the data
            this._data[front] = undefined;

            // calculate the new front of the queue
            this._front = (front   1) & (this._size - 1);

            // reduce the size
            this._length = this._length - 1;

            // return the value
            return ret;

        }

      unshift (item) {
            // get the size
            var size = this._size;

            // calculate the new front
            var i = (((( this._front - 1 ) & ( size - 1) ) ^ size ) -
            size );

            // add the item
            this._data[i] = item;

            // increment the length
            this._length = this._length   1;

            // update the new front
            this._front = i;

            // return the acknowledgement of the addition of the new
            item
            return this._length;
        }
    }

    return CircularDequeue;
})();

module.exports = CircularDequeue;

I have tried to understand this logic but the use of bitwise & in calculating the values of var i instead of modulo operator(%) keeps confusing me

CodePudding user response：

In this code something & (size - 1) is equivalent to something % size because size is a power of 2, and seeing the comment in the constructor, it is supposed to be a power of 2.

I don't see a good reason why the following has been done:

(((( this._front - 1 ) & ( size - 1) ) ^ size ) - size )

The first part ( this._front - 1 ) & ( size - 1) is always going to be a non-negative number that is less than size.

^ size will set a bit that is 0 (because the intermediate value is less than size) and then - size will clear that same bit again. So that ^ size ) - size part is a non-operation. It can be left out.

It is unclear why the author of this code preferred to work with the & operator than the %, as the latter one would also work if the size would not have been a power of two, while the & operator will only work as intended when size is a power of 2.

To see how & works, take for example that the left side is 1025, which means it is out of range. In binary 1025 is 10000000001. On the other hand we have size which is 1024. size - 1 in binary is 1111111111.

So we have this & operation:

10000000001
 1111111111
----------- &
 0000000001

So this operation effectively removes any excess bits from the left side operand, whether they come from a negative value or from a value that is not less than size.