如何在 Javascript 中创建位数组？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/6972717/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How do I create bit array in Javascript?
提问by DrStrangeLove
What is the best way of implementing a bit array in JavaScript?
在 JavaScript 中实现位数组的最佳方法是什么？
采纳答案by Brian
Here's one I whipped up:
这是我掀起的一个：
UPDATE - something about this class had been bothering me all day - it wasn't size based - creating a BitArray with N slots/bits was a two step operation - instantiate, resize. Updated the class to be size based with an optional second paramter for populating the size based instance with either array values or a base 10 numeric value.
更新 - 关于这个类的一些事情整天困扰着我 - 它不是基于大小的 - 创建一个带有 N 个插槽/位的 BitArray 是一个两步操作 - 实例化，调整大小。将类更新为基于大小的可选第二个参数，用于使用数组值或基数为 10 的数值填充基于大小的实例。
(Fiddle with it here)
（在这里摆弄它）
/* 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;
};
CREDIT TO @Daniel Baulig for asking for the refactor from quick and dirty to prototype based.
感谢@Daniel Baulig 要求重构从快速和肮脏到基于原型。
回答by beatgammit
I don't know about bit arrays, but you can make byte arrays easy with new features.
我不了解位数组，但您可以使用新功能使字节数组变得容易。
Look up typed arrays. I've used these in both Chrome and Firefox. The important one is Uint8Array.
查找类型化数组。我在 Chrome 和 Firefox 中都使用过这些。重要的是 Uint8Array。
To make an array of 512 uninitialized bytes:
要创建一个包含 512 个未初始化字节的数组：
var arr = new UintArray(512);
And accessing it (the sixth byte):
并访问它（第六个字节）：
var byte = arr[5];
For node.js, use Buffer(server-side).
对于 node.js，使用Buffer（服务器端）。
EDIT:
编辑：
To access individual bits, use bit masks.
要访问单个位，请使用位掩码。
To get the bit in the one's position, do num & 0x1
为了让位处于自己的位置，请执行 num & 0x1
回答by Benny Neugebauer
The Stanford Javascript Crypto Library (SJCL)provides a Bit Array implementation and can convert different inputs (Hex Strings, Byte Arrays, etc.) to Bit Arrays.
的斯坦福的Javascript加密库（SJCL）提供了一个位序列实现，并且可以不同的输入（十六进制字符串，字节数组等）转换成比特列。
Their code is public on GitHub: bitwiseshiftleft/sjcl. So if you lookup bitArray.js, you can find their bit array implementation.
他们的代码在 GitHub 上是公开的：bitwiseshiftleft/sjcl。因此，如果您查找bitArray.js，您可以找到它们的位数组实现。
A conversion from bytes to bits can be found here.
可以在此处找到从字节到位的转换。
回答by Commi
Something like this is as close as I can think of. Saves bit arrays as 32 bit numbers, and has a standard array backing it to handle larger sets.
像这样的事情是我能想到的最接近的事情。将位数组保存为 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
*/
回答by John Henry
Probably [definitely] not the most efficient way to do this, but a string of zeros and ones can be parsed as a number as a base 2 number and converted into a hexadecimal number and finally a buffer.
可能 [绝对] 不是最有效的方法，但是一串零和一可以被解析为一个数字作为基数为 2 的数字并转换为十六进制数，最后转换为缓冲区。
const bufferFromBinaryString = (binaryRepresentation = '01010101') =>
Buffer.from(
parseInt(binaryRepresentation, 2).toString(16), 'hex');
Again, not efficient; but I like this approach because of the relative simplicity.
同样，效率不高；但我喜欢这种方法，因为它相对简单。
回答by somatoma
Thanks for a wonderfully simple class that does just what I need.
感谢您提供一个非常简单的课程，它可以满足我的需求。
I did find a couple of edge-case bugs while testing:
我在测试时确实发现了一些边缘情况的错误：
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()
}
})
My final implementation fixed the above bugs and changed the backArray to be a Uint8Array instead of Array, which avoids signed int bugs.
我的最终实现修复了上述错误并将 backArray 更改为 Uint8Array 而不是 Array，从而避免了签名 int 错误。
回答by Rattenfengar
You can easily do that by using bitwise operators. It's quite simple. Let's try with the number 75.
您可以使用按位运算符轻松地做到这一点。这很简单。让我们试试数字 75。
Its representation in binary is 100 1011. So, how do we obtain each bit from the number? You can use an AND "&" operator to select one bit and set the rest of them to 0. Then with a Shift operator, you remove the rest of 0 that doesn't matter at the moment.
它的二进制表示是 100 1011。那么，我们如何从数字中获得每一位呢？您可以使用 AND "&" 运算符来选择一位并将其余的设置为 0。然后使用 Shift 运算符，您可以删除目前无关紧要的 0 的其余部分。
Example:
例子：
Let's do an AND operation with 4 (000 0010)
0100 1011 & 0000 0010 => 0000 0010
Now we need to filter the selected bit, in this case, was the second-bit reading right to left.
现在我们需要过滤选定的位，在这种情况下，是从右到左读取的第二位。
0000 0010 >> 1 => 1
The zeros on the left are no representative. So the output will be the bit we selected, in this case, the second one.
左边的零不代表。所以输出将是我们选择的位，在这种情况下，是第二位。
var word=75;
var res=[];
for(var x=7; x>=0; x--){
res.push((word&Math.pow(2,x))>>x);
}
console.log(res);
The output:
输出：
Expected:
预期的：
In case you need more than a simple number, you can apply the same function for a byte. Let's say you have a file with multiple bytes. So, you can decompose that file in a ByteArray, then each byte in the array in a BitArray.
如果您需要的不仅仅是一个简单的数字，您可以对一个字节应用相同的功能。假设您有一个包含多个字节的文件。因此，您可以将该文件分解为 ByteArray，然后将数组中的每个字节分解为 BitArray。
Good luck!
祝你好运！
