如何在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,请使用Buffer(服务器端).

编辑:

要访问各个位,请使用位掩码.

为了得到一个人的位置,做 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

像这样的事情是我能想到的最接近的事情。将位数组保存为 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 5

的斯坦福的Javascript加密库(SJCL)提供了一个位序列实现,并且可以不同的输入(十六进制字符串,字节数组等)转换成比特列.

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

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