如何高效地从字节中读取位？

Question

我正在开发一个包含WebSockets的项目，服务器(Node.js)和客户端(Chrome)之间的数据通过我设置的自定义（非常简单）数据交换格式进行发送。

由于我发送的项均有8个可能性，因此我将它们拆分成3位组。数据格式如下：

            0          1
bit index   01234567 8901...
item        aaabbbcc cddd...

目前，我正在像这样从字节中解析项目：

var itemA = bytes[0] >> 5;
var itemB = (bytes[0] >> 2) & 7;
var itemC = (bytes[0] & 3) << 1 | bytes[1] >> 7;
var itemD = (bytes[1] >> 4) & 7;

个人而言，我认为这过于复杂了。问题在于我得到的数据是字节，其长度是8的倍数。要解析出3位的元素，我必须进行位移、按位与操作，而因为8不能被3整除，有时我甚至还要组合两个字节的部分（如itemC）。

将数据分组读取3位比分组读取8位要更有效率。

我的解决思路是将所有的字节转换为字符串，并使用.toString(2)方法将它们转换为二进制数的字符串表示形式，然后使用.substring方法截取3位的子字符串，并使用parseInt(bitString, 2)将截取出来的字符串再转换成数字。但我想这并不是最好的方法，因为字符串的操作速度较慢，而且实际上我并没有涉及任何与字符串相关的操作。

是否有可能以例如3位的分组方式读取比特，而不是从字节中解析？或者是否有更有效的方法从字节中读取比特？

- pimvdb

Answer 1

二进制的AND和位移操作是执行这个任务最快速的方法。它们能够很好地转换成二进制指令。唯一能进一步提高速度的方法，就是牺牲带宽以获得速度，例如只使用每个字节不超过3个位，但从你的问题来看，你可能已经考虑并拒绝了这种权衡。

- Marcel Offermans

---

你是在暗示说，无论如何都无法摆脱字节中始终存在的8的倍数吗？ - pimvdb

这就是计算机的工作原理，使用字节（8位）和其倍数（16、32、64位），因此即使高级语言允许您使用其他内容，最终这些指令也需要被翻译成这些位数。 - Marcel Offermans

我一直认为在JS中位运算很无聊，因为JS只知道64位浮点数，其他都是以软件方式模拟的。经过这些年，这个旧真理是否变得不正确了呢？ - Mathias Dolidon

Answer 2

function byte2bits(a)
{
    var tmp = "";
    for(var i = 128; i >= 1; i /= 2)
        tmp += a&i?'1':'0';
    return tmp;
}
function split2Bits(a, n)
{
    var buff = "";
    var b = [];
    for(var i = 0; i < a.length; i++)
    {
        buff += byte2bits(a[i]);
        while(buff.length >= n)
        {
            b.push(buff.substr(0, n));
            buff = buff.substr(n);
        }
    }
    return [b, buff];
}
var a, b, r;
a = [227, 142];
[b, r] = split2Bits(a, 3);
//b = ["111", "000", "111", "000", "111"];
//r = '0'; //rest of bits

- wasikuss

Answer 3

我们可以通过获取适当的16位整数并对其进行位移来获得所需的值。

很明显，要获取第i个值，我们应该获取偏移量在字节中适合(bits*(i+1)-16)/8<=offset<=(bits*i)/8的16位整数。

让我们取M=bits*i/8，因此我们有M+bits/8-2<=offset<=M。然后，我们将最小偏移量作为ceil(M+bits/8-2)并通过偏移量计算第i个值在16位整数中的位置。我刚刚写了以下函数

function getDataFromStream(buffer, bitsPerValue, endianness) {
    var valuesCount = Math.floor(buffer.length * 8 / bitsPerValue);
    var ret = new Buffer(valuesCount);

    if (valuesCount > 0) {
        for (var i = 0; i < valuesCount; i++) {
            var offsetMin = Math.ceil(bitsPerValue * i / 8. + bitsPerValue / 8. - 2);
            if (offsetMin < 0) {
                offsetMin = 0;
            }
            if(endianness == 'BE')
                var wordWithValue = buffer.readUInt16BE(offsetMin, true);
            else
                var wordWithValue = buffer.readUInt16LE(offsetMin, true); 
            var offsetInWord = bitsPerValue * i - offsetMin * 8;
            var leftInWord = 16 - bitsPerValue - offsetInWord;

            // then get value in the word by shifting and then remove other bits by "%"
            ret[i] = (wordWithValue >> (endianness == 'BE' ? leftInWord : offsetInWord ))  % Math.pow(2, bitsPerValue);
        }
    }
    return ret;
}

以下是一个例子，从长度为5字节的缓冲区中读取8个5位值。

// buffer with 5 bytes
var xx = new Buffer(5);
xx[0] = 255;
xx[1] = 255;
xx[2] = 255;
xx[3] = 255;
xx[4] = 250;

// get data, 5bits per value.
var yy = getDataFromStream(xx, 5, 'BE');
console.log('got buffer with length='+ yy.length);
for(i = 0; i < yy.length; i++){
    console.log(i+'-'+yy[i]);
}

当我运行命令“node test.js”时，我得到了以下输出：

got buffer with length=8
0-31
1-31
2-31
3-31
4-31
5-31
6-31
7-26

- shukshin.ivan

---

我在使用大于255的值时遇到了问题。你能否提供一些更新？ - Geert-Jan

@Geert-Jan 但一个字节只能是0-255。你想从我的代码中得到什么？=) - shukshin.ivan

我正在寻找一些通用的编码/解码函数，以对任意长度的值进行位打包。例如：有时我会有一个值数组，其中最大值为220。其他时候可能是1045。要编码后面的数组，我需要每个项目11位（因此> 8）。不过这并不在原始问题的范围内;) - Geert-Jan

六年前，我看着这段代码就像你现在一样 :) 你只需要添加转换成字节的功能。 - shukshin.ivan

Answer 4

如果大小端兼容已经处理好了，你可以将它视为整型或长整型数组来访问。还有一种可能是不使用第三位和第七位的比特位。

- alvin

Answer 5

如果您有一个固定长度的数字（即您始终可以保证它将是2个字节），则可以按如下方式读取位：

// convert to binary
const num = 256;
const numAsBinaryString = num.toString(2);
const leastSignificantByteAsBinaryString = numAsBinaryString.substr(8);

const [
    eighthBit,
    seventhBit,
    sixthBit,
    fifthBit,
    fourthBit,
    thirdBit,
    secondBit,
    firstBit,
] = leastSignificantByteAsBinaryString.join('');

- colefner

Answer 6

我知道的最短的方法是这样的：

function isBitSet(value, bit) {
    return !!(bit === 1 ? value & 1 : value & Math.pow(2,bit));
}

这是假设value是一个“大端”字节（数字的左侧在内存中写入在右侧之前）。如果不是，你需要先进行转换。

这个函数也适用于任何位数的数字（16、32、64...）。

工作原理： 因为每个位从最右边开始，表示一个等效的“十进制”值，等于2（表示二进制系统中的2个符号）的位位置的幂次方（从1开始计数，第一个位只是1）- 如果该位被设置，与原始值进行AND运算将始终返回一个非零值 - Math.pow的结果（也是真值），如果没有设置则为0（假值）。

- Yuval A.