在JavaScript中实现位数组的最佳方法是什么？
如何在Javascript中创建位数组？
37
- DrStrangeLove
3
7您能描述一下您所面临的问题吗？ - Bill the Lizard
6没问题，这只是为了学习目的。 - DrStrangeLove
1你可能能够模仿位数组，但我认为每个数组元素仍然存储在字节中，因此你不会获得内存优势。 - vol7ron
10个回答
16
我写了一个：
更新 - 这个类的某些东西一直在困扰着我 - 它不是基于大小的 - 创建具有N个插槽/位的BitArray是一个两步操作 - 实例化，调整大小。将该类更新为基于大小，可选第二个参数用于使用数组值或十进制数值填充基于大小的实例。
(在这里试试)
/* 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提出重构的建议，从快速而肮脏的代码转变为基于原型的代码。
- Brian
20
+1。但是你能否请注释一下你的方法？还有，.ctor是什么？ - DrStrangeLove
1你应该绝对将这些方法添加到
BitArray.prototype 而非 this。 - Daniel Baulig1是的，这就是我的意思。这很重要，因为否则每个BitArray都将有自己的一组函数，这些函数将在每次调用构造函数时创建。这将以各种方式影响性能（例如内存使用，更糟糕的JIT编译等）。此外，我认为您无法知道使用您的代码的任何人是否想要增强其原型或从中继承，当使用此错误的面向对象模式时，这两者都不容易实现。 - Daniel Baulig
4我知道这个答案非常老，但我觉得强调一下很重要，这不是一个“位数组”，而是一个由“位”组成的数组。 - Nick Zuber
2一个比特数组通常会将位有效地打包到内存中，而不是存储
boolean 值，后者通常会浪费 4 字节 = 3100% 的内存。@Commi的答案解决了这个问题。 - Carl Walsh显示剩余15条评论
15
- beatgammit
5
1你会如何处理在广泛使用的浏览器中，例如IE或Firefox 3.6？ - Jiri Kriz
Firefox 3.6 应该能正常运行。对于IE，请使用普通数组，并确保只放入整数。位掩码仍然适用。 - beatgammit
13我会完全忽略旧版浏览器。如果用户在使用旧版浏览器，只需告诉他们：“抱歉，请下载一个真正的浏览器。这里是几个链接……”。这将对整个世界有益 =D - beatgammit
4这个问题应该是“Uint8Array”吗？你需要指定每个元素的位数。“UintArray”在Chrome中不存在。 - Carl Walsh
2也许Uint8ClampedArray会更好：它可以夹住数字 :) 只是一点提示。 - Infigon
7
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
- Vincent
6
我能想到的最接近的方法是这样的。将位数组保存为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
*/
- Commi
1
1这个实现中有一个错误。每31个边界上的位会给出错误的结果（即当索引为
(32 * index - 1)时，如31、63、95等）。我在get()方法中通过将>0替换为!=0来修复了它。
这个bug的原因是整数是32位有符号的。将1左移31位会得到一个负数。由于检查是>0，所以这将是错误的，而应该是true。 - amortaza6
斯坦福JavaScript加密库（SJCL）提供了位数组实现，并可以将不同的输入（十六进制字符串，字节数组等）转换为位数组。
他们的代码在GitHub上公开：bitwiseshiftleft/sjcl。因此，如果您查找bitArray.js，您可以找到他们的位数组实现。
从字节到位的转换可以在这里找到。
- Benny Code
1
2022
我们可以通过扩展DataView来实现类似于TypedArray的BitArray类。然而，为了避免使用Proxy陷阱直接访问数值属性（索引）的成本，我认为最好保持在DataView领域内。如今，DataView比TypedArray更受青睐，因为它在最近的V8版本（v7+）中性能得到了极大的提升。
与TypedArray一样，在构造时BitArray将具有预定长度。下面的代码片段中包含了一些方法。 popcnt属性可以非常高效地返回BitArray中1的总数。与普通数组不同，popcnt是BitArrays中非常受欢迎的功能。以至于Web Assembly甚至现代CPU都有专门的pop count指令。除此之外，如果需要，您还可以轻松添加像.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);
我希望这有所帮助。
- Redu
7
恭喜您不断更新（我非常喜欢您的方法，胜过其他答案）！您能否添加布尔运算到数组中？And(), Not(), Or()和Xor()似乎是很重要的补充。 - Atriace
1请参见https://en.wikipedia.org/wiki/Bit_array#Basic_operations。像`and`这样的布尔运算可以特别有用，可以快速找到两个数组具有相同值的位置。同样，`or`将告诉您任何位是否为正数。这种操作是Matt Parker在他的wordle挑战中看到400万倍加速的原因之一（请参见https://www.youtube.com/watch?v=c33AZBnRHks）。 - Atriace
1@Atriace 好的，受了一升便宜酒的影响，我已经添加了
.and(), .or(), .xor() 和 .not() 方法。希望我没有破坏任何东西。 :) 我最初的方法是 64 位的，但在测试 BitArray 大小为 1e5~1e6 时，与 32 位相比，BigInt 操作会使其减慢 ~7 倍。老实说，我真的不知道 JS 中 BigInt 是什么大不了的。然而，无论如何... 在这个任务中我们最好保持32位。 - Redu@Atriace 还有一点要提到的是，一旦这个模型变得足够成熟，就可以将
BitArray 扩展为固定大小的 BitVector128、BitVector256 或 BitVector512 类，具有 .leftShift()、.rightShift() 等方法。它的性能是足够的。 - Redu@Atriace 是的，像
and 等逻辑操作和 popcnt 也需要 32 位访问以获得高性能。因此，将大小设置为 32 位的倍数非常方便。但这不是我最大的关注点。我正在解决一些其他问题，这些问题在 BitArray 很大时会显现出来。一旦大小增长，太多的位操作会导致一些问题。一旦我解决了这些问题，我会在存储库方面与您联系。 - Redu显示剩余2条评论
1
你可以通过使用位运算符轻松实现。这很简单。让我们以数字75为例。
它的二进制表示为100 1011。那么，我们如何从数字中获取每个位呢？您可以使用AND“&”运算符选择一个位并将其余部分设置为0。然后再用移位运算符将不重要的0去掉。
现在我们需要过滤所选位，这种情况下是从右到左读取的第二位。
左边的零不具有代表性。因此，输出将是我们选择的位，即第二个位。
它的二进制表示为100 1011。那么，我们如何从数字中获取每个位呢？您可以使用AND“&”运算符选择一个位并将其余部分设置为0。然后再用移位运算符将不重要的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);
输出：
- Rattenfengar
1
@Commi的实现是我最终使用的。
我认为这个实现中存在一个bug。每31位边界上的位给出了错误的结果。(即当索引为(32 * index - 1)时，如31、63、95等)。
我在get()方法中通过将> 0替换为!= 0来修复它。
get(n) {
return (this.backingArray[n/32|0] & 1 << n % 32) != 0
}
这个错误的原因是整数是32位有符号的。将1左移31位会得到一个负数。由于检查是
>0，所以当应该为true时，这将是false。我之前写了一个程序来证明这个错误，并进行了修复。将它发布出来，已经没有空间了。
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);
}
}
}
- amortaza
0
这可能[肯定]不是最有效的方法，但是可以将一串零和一解析为一个二进制数，并转换为十六进制数，最终成为缓冲区。
const bufferFromBinaryString = (binaryRepresentation = '01010101') =>
Buffer.from(
parseInt(binaryRepresentation, 2).toString(16), 'hex');
再次强调，这种方法并不高效；但是我喜欢它的相对简单性。
- John Henry
1
1这对于非常长的比特字符串不起作用，只适用于整数。 - bryc
0
感谢提供一个非常简单的类，正好满足我的需求。
在测试过程中，我发现了一些边缘情况的错误：
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，这样可以避免带符号整数的问题。
- somatoma
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接