如何用JavaScript通过位序列做标志位（大于32位）

Question

1.我需要通过JavaScript来用位序列做标志位，来表示相对应的数据块存在或不存在，需要能够存取特定位，能够实现类似shift的移位功能，我知道在32位以内很容易实现，但是我需要实现更大的，比如说1024位（利用arraybuffer），这样在存取特定位上没有问题，但是在移位上却是有问题的，不知道有没有办法能够实现，如果有具体如何，希望能有一些指点，谢谢？(补充一点：移位的时候需要后面的位相应补位，也就是说，我的标志位是对应的一个序列，类似一一个队列的样子，只是里面的元素是通过位来标志值是否存在)

Answer 1

之前说 JavaScript 最大支持 31 位的整数，抱歉，说错了，我用 Number.MAX_SAFE_INTEGER.toString(2).length 计算了一下，结果是 53，也就是说 JavaScript 最大支持 53 位的整数。因此，我修改了答案。

可以用 Uint32Array、Uint16Array 或者 Uint8Array 来封装 ArrayBuffer 来进行处理。按习惯用 Uint32Array 或 Uint8Array 合适一些。理论上 Uint32Array 会更快，但实际上要看 ArrayBuffer 的具体实现，这里不做速度上的比较。

然后一般的位操作都直接算 index 就了，只有位移操作的时候需要计算上个位移移出的部分。

Uint8Array 实现

先写的这个答案，留在这了。后面用 Uint32Array 的实现可能更好一些。

下面写了一个左移一位的操作，为了简化测试，只字义了4个字节（按字节而不是按整数处理的，所以可以模拟多个单元的情况）

var buffer = new ArrayBuffer(4);
var iBuffer = new Uint8Array(buffer);

iBuffer[0] = 0x03;
iBuffer[1] = 0xf0;

console.log(Array.from(iBuffer).map(n => n.toString(2)));
// [ '11', '11110000', '0', '0' ]

let rest = 0;
for (let i = iBuffer.length - 1; i >= 0; i--) {
    const v = iBuffer[i];
    const newRest = (v & 0x80) > 0 ? 1 : 0;
    iBuffer[i] = ((v << 1) | rest) & 0xff;
    rest = newRest;
}

console.log(Array.from(iBuffer).map(n => n.toString(2)));
// [ '111', '11100000', '0', '0' ]

如果需要移多位，对 Uint8Array 来说，8位以内，都可以通过位移来算 newRest，比如，移3位的情况

const newRest = v >> (8 - 3);

但是对于移位大于 8 的情况就比较复杂一些了，需要计算 index 偏移（或者 8 位 8 位的移，再处理余下不足 8 位的情况）。

所以总的来说我觉得这个算法还是比较考人的，不过我没搜到合适的 BitInteger 库，只找到一个 没提供位运算的，可以试试通过乘法(×2)和除法(÷2）来实现。

又试验了一下，可以用 Uint32Array 来实现这样操作起来可能会更快一些

var buffer = new ArrayBuffer(16);
var iBuffer = new Uint32Array(buffer);

iBuffer[0] = 0x03;
iBuffer[1] = 0x8f000000;

console.log(Array.from(iBuffer).map(n => n.toString(2)));

// bits 需要小于32
function shift(buffer, bits) {
    let rest = 0;
    for (let i = iBuffer.length - 1; i >= 0; i--) {
        const v = iBuffer[i];
        const newRest = v >>> (32 - bits);
        iBuffer[i] = ((v << bits) | rest) & 0xffffffff;
        rest = newRest;
    }
}

shift(iBuffer, 5);

console.log(Array.from(iBuffer).map(n => n.toString(2)));

输出

[ '11', '10001111000000000000000000000000', '0', '0' ]
[ '1110001', '11100000000000000000000000000000', '0', '0' ]

Answer 2

1024位 就是 32个 32位整数

用一个32个元素的数组就可以实现

先判断要操作的 位 在哪个整数里，然后对那个数进行左右移位。

---

我要表示的这个标志位比较多，大概要1024位，当我左移的时候，意味着后面的位都要往前补位的，如果是以32位元素数组来做的话，我将第一个元素左移两位，后面不是会自动补两个0.而不会是第二个元素把最高两位补上来么？这样的话，就不能解决我的问题了...还是说32位的数组，其中的元素在内存上是连续的，左移第一位后面的会往前补么？

@hei_yu_fa

我的建议是：由于内存最小的访问单元是字节（byte），所以，用1个字节来表示标志位比较合适。

如果用 位（bit）来表示，每移动1位，就得跨单元修改整个内存块，效率很低。

用字节的话，可以用复合视图来模拟左右移运算，效率高，程序也容易写~

参考：ArrayBuffer：类型化数组

---

例子:
用有8个元素的作例子

//分配内存，需要三倍队列大小的空间
buf = new ArrayBuffer(8*3)

vwui8 = new Uint8Array(buf,8,8)//队列刚开始在中间
//[0, 0, 0, 0, 0, 0, 0, 0]
for (i in vwui8)vwui8[i]=1//初始化为 1

vwui8
//[1, 1, 1, 1, 1, 1, 1, 1]

//右移
vwui8[7]=0 //删除最右的元素
//[1, 1, 1, 1, 1, 1, 1, 0]
vwui8 = new Uint8Array(buf,vwui8.byteOffset-1,8)//右移 1位
//[0, 1, 1, 1, 1, 1, 1, 1]

//修改队列元素
vwui8[0]=1
//[1, 1, 1, 1, 1, 1, 1, 1]

//左移
vwui8[0]=0 //删除最左的元素
vwui8 = new Uint8Array(buf,vwui8.byteOffset+1,8) //左移 1位
//[1, 1, 1, 1, 1, 1, 1, 0]