如何在 Javascript 中创建位数组？

Question

在 JavaScript 中实现位数组的最佳方法是什么？

Answer 1

这是我提出的一个：

更新 - 关于这个类的一些事情一直困扰着我一整天 - 它不是基于大小的 - 创建一个具有 N 个插槽/位的 BitArray 是一个两步操作 - 实例化，调整大小。使用可选的第二个参数将类更新为基于大小，以便使用数组值或以 10 为基数的数值填充基于大小的实例。

（在这里摆弄它）

/* BitArray DataType */

// Constructor
function BitArray(size, bits) {
    // Private field - array for our bits
    this.m_bits = new Array();

    //.ctor - initialize as a copy of an array of true/false or from a numeric value
    if (bits && bits.length) {
        for (var i = 0; i < bits.length; i++)
            this.m_bits.push(bits[i] ? BitArray._ON : BitArray._OFF);
    } else if (!isNaN(bits)) {
        this.m_bits = BitArray.shred(bits).m_bits;

    }
    if (size && this.m_bits.length != size) {
        if (this.m_bits.length < size) {
            for (var i = this.m_bits.length; i < size; i++) {
                this.m_bits.push(BitArray._OFF);
            }
        } else {
            for(var i = size; i > this.m_bits.length; i--){
                this.m_bits.pop();
            }
        }
    }
}

/* BitArray PUBLIC INSTANCE METHODS */

// read-only property - number of bits 
BitArray.prototype.getLength = function () { return this.m_bits.length; };

// accessor - get bit at index 
BitArray.prototype.getAt = function (index) {
    if (index < this.m_bits.length) {
        return this.m_bits[index];
    }
    return null;
};
// accessor - set bit at index 
BitArray.prototype.setAt = function (index, value) {
    if (index < this.m_bits.length) {
        this.m_bits[index] = value ? BitArray._ON : BitArray._OFF;
    }
};

// resize the bit array (append new false/0 indexes) 
BitArray.prototype.resize = function (newSize) {
    var tmp = new Array();
    for (var i = 0; i < newSize; i++) {
        if (i < this.m_bits.length) {
            tmp.push(this.m_bits[i]);
        } else {
            tmp.push(BitArray._OFF);
        }
    }
    this.m_bits = tmp;
};

// Get the complimentary bit array (i.e., 01 compliments 10)
BitArray.prototype.getCompliment = function () {
    var result = new BitArray(this.m_bits.length);
    for (var i = 0; i < this.m_bits.length; i++) {
        result.setAt(i, this.m_bits[i] ? BitArray._OFF : BitArray._ON);
    }
    return result;
};

// Get the string representation ("101010") 
BitArray.prototype.toString = function () {
    var s = new String();
    for (var i = 0; i < this.m_bits.length; i++) {
        s = s.concat(this.m_bits[i] === BitArray._ON ? "1" : "0");
    }
    return s;
};

// Get the numeric value 
BitArray.prototype.toNumber = function () {
    var pow = 0;
    var n = 0;
    for (var i = this.m_bits.length - 1; i >= 0; i--) {
        if (this.m_bits[i] === BitArray._ON) {
            n += Math.pow(2, pow);
        }
        pow++;
    }
    return n;
};

/* STATIC METHODS */

// Get the union of two bit arrays
BitArray.getUnion = function (bitArray1, bitArray2) {
    var len = BitArray._getLen(bitArray1, bitArray2, true);
    var result = new BitArray(len);
    for (var i = 0; i < len; i++) {
        result.setAt(i, BitArray._union(bitArray1.getAt(i), bitArray2.getAt(i)));
    }
    return result;
};

// Get the intersection of two bit arrays 
BitArray.getIntersection = function (bitArray1, bitArray2) {
    var len = BitArray._getLen(bitArray1, bitArray2, true);
    var result = new BitArray(len);
    for (var i = 0; i < len; i++) {
        result.setAt(i, BitArray._intersect(bitArray1.getAt(i), bitArray2.getAt(i)));
    }
    return result;
};

// Get the difference between to bit arrays
BitArray.getDifference = function (bitArray1, bitArray2) {
    var len = BitArray._getLen(bitArray1, bitArray2, true);
    var result = new BitArray(len);
    for (var i = 0; i < len; i++) {
        result.setAt(i, BitArray._difference(bitArray1.getAt(i), bitArray2.getAt(i)));
    }
    return result;
};

// Convert a number into a bit array
BitArray.shred = function (number) {
    var bits = new Array();
    var q = number;
    do {
        bits.push(q % 2);
        q = Math.floor(q / 2);
    } while (q > 0);
    return new BitArray(bits.length, bits.reverse());
};

/* BitArray PRIVATE STATIC CONSTANTS */
BitArray._ON = 1;
BitArray._OFF = 0;

/* BitArray PRIVATE STATIC METHODS */

// Calculate the intersection of two bits 
BitArray._intersect = function (bit1, bit2) {
    return bit1 === BitArray._ON && bit2 === BitArray._ON ? BitArray._ON : BitArray._OFF;
};

// Calculate the union of two bits 
BitArray._union = function (bit1, bit2) {
    return bit1 === BitArray._ON || bit2 === BitArray._ON ? BitArray._ON : BitArray._OFF;
};

// Calculate the difference of two bits 
BitArray._difference = function (bit1, bit2) {
    return bit1 === BitArray._ON && bit2 !== BitArray._ON ? BitArray._ON : BitArray._OFF;
};

// Get the longest or shortest (smallest) length of the two bit arrays 
BitArray._getLen = function (bitArray1, bitArray2, smallest) {
    var l1 = bitArray1.getLength();
    var l2 = bitArray2.getLength();

    return l1 > l2 ? smallest ? l2 : l1 : smallest ? l2 : l1;
};

感谢@Daniel Baulig要求从快速而肮脏的重构到原型基于。

Answer 2

我不了解位数组，但您可以通过新功能使字节数组变得简单。

查找类型化数组。我在 Chrome 和 Firefox 中都使用过这些。重要的是Uint8Array。

要创建 512 个未初始化字节的数组：

var arr = new UintArray(512);

并访问它（第六个字节）：

var byte = arr[5];

对于 node.js，请使用 缓冲区（服务器端）。

编辑：

要访问各个位，请使用位掩码。

要获取该位的位置，请执行 num & 0x1

Answer 3

2022

从过去的答案和评论中可以看出，“实现位数组”的问题可以用两种不同的（非排他性）方式来理解：

• 一个在内存中占用 1 位的数组每个条目都是
• 一个可以应用按位运算的数组

正如 @beatgammit 指出的那样，ecmascript 指定 类型化数组，但位数组不属于其中。我刚刚发布了 @bitarray/typedarray，这是位类型化数组的实现，模拟本机类型化数组并每个条目在内存中占用 1 位。

因为它重现了本机类型数组的行为，所以它不包含任何按位操作。因此，我还发布了 @bitarray/es6，它通过按位运算扩展了之前的内容强>。

根据所提出的问题，我不会争论实现位数组的最佳方式是什么，因为“最佳”可以进行详细争论，但这些肯定是一些实现位数组的方法，其优点是它们的行为类似于本机类型数组。

import BitArray from "@bitarray/es6"

const bits1 = BitArray.from("11001010");
const bits2 = BitArray.from("10111010");
for (let bit of bits1.or(bits2)) console.log(bit) // 1 1 1 1 1 0 1 0

Answer 4

斯坦福 Javascript 加密库 (SJCL) 提供位数组实现，可以转换不同的输入（十六进制字符串、字节数组等）到位数组。

他们的代码在 GitHub 上公开：bitwiseshiftleft/sjcl。因此，如果您查找 bitArray.js，您可以找到他们的位数组实现。

从字节到位的转换可以在此处。

Answer 5

我能想到的最接近的事情就是这样。将位数组保存为 32 位数字，并有一个标准数组支持它来处理更大的集合。

class bitArray {
  constructor(length) {
    this.backingArray = Array.from({length: Math.ceil(length/32)}, ()=>0)
    this.length = length
  }
  get(n) {
    return (this.backingArray[n/32|0] & 1 << n % 32) > 0
  }
  on(n) {
    this.backingArray[n/32|0] |= 1 << n % 32
  }
  off(n) {
    this.backingArray[n/32|0] &= ~(1 << n % 32)
  }
  toggle(n) {
    this.backingArray[n/32|0] ^= 1 << n % 32
  }
  forEach(callback) {
    this.backingArray.forEach((number, container)=>{
      const max = container == this.backingArray.length-1 ? this.length%32 : 32
      for(let x=0; x<max; x++) {
        callback((number & 1<<x)>0, 32*container+x)
      }
    })
  }
}
let bits = new bitArray(10)
bits.get(2) //false
bits.on(2)
bits.get(2) //true

bits.forEach(console.log) 
/* outputs:
false
false
true
false
false
false
false
false
false
false
*/

bits.toggle(2)

bits.forEach(console.log) 
/* outputs:
false
false
false
false
false
false
false
false
false
false
*/

bits.toggle(0)
bits.toggle(1)
bits.toggle(2)

bits.off(2)
bits.off(3)
bits.forEach(console.log) 
/* outputs:
true
true
false
false
false
false
false
false
false
false
*/

Answer 6

2022

我们可以通过扩展 DataView。但是，为了避免使用代理捕获对数字属性（索引）的直接访问的成本，我认为最好留在DataView域中。无论如何，现在 DataView 比 TypedArray 更好，因为它的性能在最近的 V8 版本 (v7+) 中得到了极大的提高。

就像 TypedArray 一样，BitArray 在构造时将具有预定的长度。我只是在下面的代码片段中包含了一些方法。 popcnt 属性非常有效地返回 BitArray 中 1 的总数。与普通数组不同，popcnt 是 BitArray 备受追捧的功能。以至于 Web Assembly 甚至现代 CPU 都有专用的弹出计数指令。除此之外，如果需要，您还可以轻松添加 .forEach()、.map() 等方法。

class BitArray extends DataView{

  constructor(n,ab){
    if (n > 1.5e10) throw new Error("BitArray size can not exceed 1.5e10");
    super(ab instanceof ArrayBuffer ? ab
                                    : new ArrayBuffer(Number((BigInt(n + 31) & ~31n) >> 3n))); // Sets ArrayBuffer.byteLength to multiples of 4 bytes (32 bits)
  }

  get length(){
    return this.buffer.byteLength << 3;
  }

  get popcount(){
    var m1  = 0x55555555,
        m2  = 0x33333333,
        m4  = 0x0f0f0f0f,
        h01 = 0x01010101,
        pc  = 0,
        x;
    for (var i = 0, len = this.buffer.byteLength >> 2; i < len; i++){
       x = this.getUint32(i << 2);
       x -= (x >> 1) & m1;             //put count of each 2 bits into those 2 bits
       x = (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits
       x = (x + (x >> 4)) & m4;        //put count of each 8 bits into those 8 bits
       pc += (x * h01) >> 56;
    }
    return pc;
  }

  // n >> 3 is Math.floor(n/8)
  // n & 7 is n % 8

  and(bar){
    var len = Math.min(this.buffer.byteLength,bar.buffer.byteLength),
        res = new BitArray(len << 3);
    for (var i = 0; i < len; i += 4) res.setUint32(i,this.getUint32(i) & bar.getUint32(i));
    return res;
  }

  at(n){  
    return this.getUint8(n >> 3) & (1 << (n & 7)) ? 1 : 0;
  }
  
  or(bar){
    var len = Math.min(this.buffer.byteLength,bar.buffer.byteLength),
        res = new BitArray(len << 3);
    for (var i = 0; i < len; i += 4) res.setUint32(i,this.getUint32(i) | bar.getUint32(i));
    return res;
  }
  
  not(){
    var len = this.buffer.byteLength,
        res = new BitArray(len << 3);
    for (var i = 0; i < len; i += 4) res.setUint32(i,~(this.getUint32(i) >> 0));
    return res;
  }

  reset(n){
    this.setUint8(n >> 3, this.getUint8(n >> 3) & ~(1 << (n & 7)));
  }

  set(n){
    this.setUint8(n >> 3, this.getUint8(n >> 3) | (1 << (n & 7)));
  }

  slice(a = 0, b = this.length){
    return new BitArray(b-a,this.buffer.slice(a >> 3, b >> 3));
  }

  toggle(n){
    this.setUint8(n >> 3, this.getUint8(n >> 3) ^ (1 << (n & 7)));
  }

  toString(){
    return new Uint8Array(this.buffer).reduce((p,c) => p + ((BigInt(c)* 0x0202020202n & 0x010884422010n) % 1023n).toString(2).padStart(8,"0"),"");
  }
  
  xor(bar){
    var len = Math.min(this.buffer.byteLength,bar.buffer.byteLength),
        res = new BitArray(len << 3);
    for (var i = 0; i < len; i += 4) res.setUint32(i,this.getUint32(i) ^ bar.getUint32(i));
    return res;
  }
}

就像我希望它有帮助一样

var u = new BitArray(12);

。

Answer 7

您可以使用按位运算符轻松地做到这一点。这很简单。
让我们尝试一下数字 75。

它的二进制表示是 100 1011。那么，我们如何从该数字中获取每一位呢？
您可以使用 AND“&”运算符选择一位并将其余的设置为 0。然后使用 Shift 运算符，删除目前不重要的其余 0。

示例：

Let's do an AND operation with 4 (000 0010)

0100 1011 & 0000 0010 => 0000 0010

现在我们需要过滤选定的位，在本例中，是从右向左读取的第二位。

0000 0010 >> 1 => 1

左边的零不具有代表性。因此输出将是我们选择的位，在本例中是第二位。

var word=75;
var res=[];
for(var x=7; x>=0; x--){
  res.push((word&Math.pow(2,x))>>x);
}
console.log(res);

输出：

预期：

如果您需要的不仅仅是一个简单的数字，您可以对一个字节应用相同的函数。假设您有一个包含多个字节的文件。因此，您可以将该文件分解为 ByteArray，然后将数组中的每个字节分解为 BitArray。

祝你好运！

Answer 8

@Commi 的实现是我最终使用的。

我相信这个实现中有一个错误。每第 31 个边界上的位都会给出错误的结果。 （即当索引为 (32 * index - 1) 时，即 31、63、95 等。

我在 get() 方法中通过将 > 0 替换为!= 0

get(n) {
    return (this.backingArray[n/32|0] & 1 << n % 32) != 0
}

的原因是整数是 32 位有符号的，因为检查是针对的。 >0，当它应该是真的时，这将是错误的。

我之前编写了一个程序来证明该错误，并且之后的修复将在空间不足时发布。

for (var i=0; i < 100; i++) {
  var ar = new bitArray(1000);
  
  ar.on(i);

  for(var j=0;j<1000;j++) {

    // we should have TRUE only at one position and that is "i". 
    // if something is true when it should be false or false when it should be true, then report it.

    if(ar.get(j)) {
      if (j != i) console.log('we got a bug at ' + i);
    } 

    if (!ar.get(j)) {
      if (j == i) console.log('we got a bug at ' + i);
    }
  }
}

Answer 9

也许[绝对]不是最有效的方法，但一串零和一可以解析为以 2 为基数的数字，并转换为十六进制数字，最后转换为缓冲区。

const bufferFromBinaryString = (binaryRepresentation = '01010101') =>
    Buffer.from(
        parseInt(binaryRepresentation, 2).toString(16), 'hex');

再次，效率不高；但我喜欢这种方法，因为它相对简单。

Answer 10

感谢您提供了一个非常简单的课程，它满足了我的需要。

我在测试时确实发现了一些边缘情况错误：

get(n) {
    return (this.backingArray[n/32|0] & 1 << n % 32) != 0
    // test of > 0 fails for bit 31
}

forEach(callback) {
    this.backingArray.forEach((number, container)=>{
        const max = container == this.backingArray.length-1 && this.length%32
            ? this.length%32 : 32;
            // tricky edge-case: at length-1 when length%32 == 0,
            // need full 32 bits not 0 bits
    for(let x=0; x<max; x++) {
        callback((number & 1<<x)!=0, 32*container+x) // see fix in get()
    }
})

我的最终实现修复了上述错误，并将 backArray 更改为 Uint8Array 而不是 Array，这避免了signed int bug。