int 到 2 个字节的可变长度编码
Variable length-encoding of int to 2 bytes
我正在实施可变长度编码并阅读 wikipedia 相关内容。这是我发现的:
0x00000080 0x81 0x00
表示0x80
int被编码为0x81 0x00
2个字节。那是我无法理解的。好的,按照那里列出的算法我们有。
- 二进制
0x80
:00000000 00000000 00000000 10000000
我们将符号位移动到下一个八位位组,因此我们有并设置为 1(表示我们有更多八位位组):
00000000 00000000 00000001 10000000
不等于 0x81 0x00
。我试图为此编写一个程序:
byte[] ba = new byte[]{(byte) 0x81, (byte) 0x00};
int first = (ba[0] & 0xFF) & 0x7F;
int second = ((ba[1] & 0xFF) & 0x7F) << 7;
int result = first | second;
System.out.println(result); //prints 1, not 0x80
我错过了什么?
让我们回顾一下来自维基百科页面的算法:
- 取整数的二进制表示
- 将其分成7位一组,具有最高值的组将更少
- 将这七位作为一个字节,将MSB(最高有效位)设置为1,除了最后一位;最后一个留0
我们可以这样实现算法:
public static byte[] variableLengthInteger(int input) {
// first find out how many bytes we need to represent the integer
int numBytes = ((32 - Integer.numberOfLeadingZeros(input)) + 6) / 7;
// if the integer is 0, we still need 1 byte
numBytes = numBytes > 0 ? numBytes : 1;
byte[] output = new byte[numBytes];
// for each byte of output ...
for(int i = 0; i < numBytes; i++) {
// ... take the least significant 7 bits of input and set the MSB to 1 ...
output[i] = (byte) ((input & 0b1111111) | 0b10000000);
// ... shift the input right by 7 places, discarding the 7 bits we just used
input >>= 7;
}
// finally reset the MSB on the last byte
output[0] &= 0b01111111;
return output;
}
您可以看到它适用于维基百科页面 here 中的示例,您也可以插入您自己的值并在线尝试。
另一种整数的可变长度编码存在并被广泛使用。例如,1984 年的 ASN.1 确实 define "length" field 为:
The encoding of length can take two forms: short or long. The short
form is a single byte, between 0 and 127.
The long form is at least two bytes long, and has bit 8 of the first
byte set to 1. Bits 7-1 of the first byte indicate how many more bytes
are in the length field itself. Then the remaining bytes specify the
length itself, as a multi-byte integer.
此编码用于 DLMS COSEM 协议或 https 证书等示例。对于简单的代码,你可以看看ASN.1 java library.
我正在实施可变长度编码并阅读 wikipedia 相关内容。这是我发现的:
0x00000080 0x81 0x00
表示0x80
int被编码为0x81 0x00
2个字节。那是我无法理解的。好的,按照那里列出的算法我们有。
- 二进制
0x80
:00000000 00000000 00000000 10000000
我们将符号位移动到下一个八位位组,因此我们有并设置为 1(表示我们有更多八位位组):
00000000 00000000 00000001 10000000
不等于0x81 0x00
。我试图为此编写一个程序:byte[] ba = new byte[]{(byte) 0x81, (byte) 0x00}; int first = (ba[0] & 0xFF) & 0x7F; int second = ((ba[1] & 0xFF) & 0x7F) << 7; int result = first | second; System.out.println(result); //prints 1, not 0x80
我错过了什么?
让我们回顾一下来自维基百科页面的算法:
- 取整数的二进制表示
- 将其分成7位一组,具有最高值的组将更少
- 将这七位作为一个字节,将MSB(最高有效位)设置为1,除了最后一位;最后一个留0
我们可以这样实现算法:
public static byte[] variableLengthInteger(int input) {
// first find out how many bytes we need to represent the integer
int numBytes = ((32 - Integer.numberOfLeadingZeros(input)) + 6) / 7;
// if the integer is 0, we still need 1 byte
numBytes = numBytes > 0 ? numBytes : 1;
byte[] output = new byte[numBytes];
// for each byte of output ...
for(int i = 0; i < numBytes; i++) {
// ... take the least significant 7 bits of input and set the MSB to 1 ...
output[i] = (byte) ((input & 0b1111111) | 0b10000000);
// ... shift the input right by 7 places, discarding the 7 bits we just used
input >>= 7;
}
// finally reset the MSB on the last byte
output[0] &= 0b01111111;
return output;
}
您可以看到它适用于维基百科页面 here 中的示例,您也可以插入您自己的值并在线尝试。
另一种整数的可变长度编码存在并被广泛使用。例如,1984 年的 ASN.1 确实 define "length" field 为:
The encoding of length can take two forms: short or long. The short form is a single byte, between 0 and 127.
The long form is at least two bytes long, and has bit 8 of the first byte set to 1. Bits 7-1 of the first byte indicate how many more bytes are in the length field itself. Then the remaining bytes specify the length itself, as a multi-byte integer.
此编码用于 DLMS COSEM 协议或 https 证书等示例。对于简单的代码,你可以看看ASN.1 java library.