Javascript 中的循环队列

Question

当我找到这段代码时，我正在阅读一本关于数据结构和算法的书 JavaScript。

我需要有人帮我解释一下代码背后的逻辑，以及每个方法中 var i 值背后的逻辑。

var i = (this._front + length) & (this._size - 1); //explain this in push()
var i = (this._front + length - 1) & (this._size - 1); // explain this in pop()
var i = (((( this._front - 1 ) & ( size - 1) ) ^ size ) - size );// explain this in unshift()

请解释每个方法的一般逻辑，我对上述语句中 & 运算符的使用有疑问，请问为什么使用 & 而不是 %

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;

我试图理解这个逻辑，但是在计算 var i 的值时使用按位 & 而不是模运算符 (%) 让我感到困惑

Answer 1

这段代码中something & (size - 1)等价于something % size，因为size是2的幂，看构造函数中的注释，应该是2的幂.

我没有看到完成以下操作的充分理由：

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

第一部分 ( this._front - 1 ) & ( size - 1) 是总是将是一个小于 size.

的 non-negative 数字

^ size 将设置为 0 的位（因为中间值比 size 少 ) 然后 - size 将再次清除相同的位。所以 ^ size ) - size 部分是 non-operation。可以省略。

不清楚为什么此代码的作者更喜欢使用 & 运算符而不是 %，因为后者也可以工作如果大小不是 2 的幂，而 & 运算符只会在 size 是 2 的幂时按预期工作。

要看&是如何工作的，以左边为1025为例，表示超出范围。在二进制中，1025 是 10000000001。另一方面，我们有 size，即 1024。size - 1 在二进制中是 1111111111。

所以我们有这个 & 操作：

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

因此，此操作有效地从左侧操作数中删除了任何多余的位，无论它们来自负数值还是来自不小于 size 的值.

Javascript 中的循环队列

Circular Queue in Javascript

javascript

algorithm

data-structures

circular-queue