通过上一章内容，我们应该对位运算有了基本的认识，但是位运算的妙用远不止于此，本章我们就通过自己实现变长整型的方式更深刻地了解一下位运算在编程上带来了优势。
内存压缩和高效存储是程序员绕不开的话题，而变长存储在某些方面很好的解决了这个问题。
变长整型
假设我们需要在内存中存放以下一组数据:
1,44,583,75457,4,2334,533,34,2334,533,54,3,543,65667,45433,765765435,543322,43422
首先我们会想到的是使用一个int数组，那我们来计算一下使用int数组存放需要的内存大小，以上数组长度为17，在64bit的JVM中，一个int值占用4个字节的空间，加上数组头长度16个字节，以上数组占用大小即为16 + 4 * 17 = 84，此时JVM会为此分配88（64 + 24）字节的空间。
此时精打细算的我们不禁考虑到一个问题，像以上数组中类似于1,44,4,34,3,54这些数字，实际上一个字节就可以表示了（一个byte可以表示的最大正整数为127），却都要占用4个字节的空间，有点浪费了。那有没有什么办法让我们能够根据数值的大小动态调整分配的字节空间呢？答案当然是没有了，毕竟JVM对我们屏蔽了内存操作。不过大神们却总能找到折中的优化方案，那就是变长整型。
实现原理
JAVA实现变长整型的思路是利用byte[]替代int，用每个byte的最高位做标志位，后7位为有效算术位，如果标志位为1，则说明后一个字节和当前字节是同一个数字，为0说明后一个字节是一个新的数字。（这里仅对针对非负整数数组）
使用变长整型存储以上的数组，此时JVM会为此分配56（32 + 24）字节 。如果数组长度足够大的话，使用变长存储所能节约的内存空间是非常可观的。
当然变长整型自然有它的弊端，如果数组中有大量的数值都超过268435455（变长整型设计中4个byte所能表示的最大值）的话，变长存储所耗费的内存空间甚至会远大于int数组。不过大神们永远是难不倒的，我们可以使用一种增量压缩的技巧来存储数组，即对于有序数组我们可以只存储每个数值与其前一个数值的差值，这个差值往往不会太大，这时再使用变长存储就会非常的划算（实际上这也是elasticsearch使用到的存储技巧之一）。
代码实现
以下是我自己实现的一个简单demo：
/**
* 单个整型的变长化递归实现
* @param value
* @param iv
*/
protected static void toByte(List<Byte> value, int iv) {
byte i = (byte) (iv & 0x7f);
iv = iv >> 7;
if (iv > 0) {
i = (byte) (i | 0x80);
value.add(i);
toByte(value, iv);
} else {
value.add(i);
}
}
/**
* 将int数组转化为变长数组
* @param intArray
* @return
*/
public static byte[] toVint(int[] intArray) {
ArrayList<Byte> byteArray = new ArrayList<Byte>();
for (int i = 0; i < intArray.length; i++) {
int temp = intArray[i];
if (temp < 0) {
throw new RuntimeException("数组中包含负数，无法通过");
}
toByte(byteArray, temp);
}
byte[] bytes = new byte[byteArray.size()];
for (int i = 0; i < byteArray.size(); i++) {
bytes[i] = byteArray.get(i);
}
return bytes;
}
/**
* 将变长数组转化为int数组
* @param bytes
* @return
*/
public static int[] toInt(byte[] bytes) {
ArrayList<Integer> array = new ArrayList<java.lang.Integer>();
int temp = 0;
int index = 0;
for (byte b : bytes) {
if ((b & 0x80) == 0) {
temp |= b << (index * 7);
array.add(temp);
index = 0;
temp = 0;
} else {
temp |= (b & 0x7f) << (index++ * 7);
}
}
int[] ints = new int[array.size()];
for (int i = 0; i < array.size(); i++) {
ints[i] = array.get(i);
}
return ints;
}
测试代码：
int[] a = {1, 44, 583, 75457, 4, 2334, 533, 34, 2334, 533, 54, 3, 543, 65667, 45433, 765765435, 543322, 43422};
byte[] bytes = Vint.toVint(a);
int[] ints = Vint.toInt(bytes);
for (int i = 0; i < ints.length; i++) {
System.out.println(ints[i]);
}
long l = RamUsageEstimator.sizeOf(a);
long l2 = RamUsageEstimator.sizeOf(bytes);
System.out.println("int[] 所占内存：" + l + "字节");
System.out.println("vint 所占内存：" + l2 + "字节");
输出结果：
int[] 所占内存：88字节
vint 所占内存：56字节
以上代码的关键之处就在于位运算的操作，取一段为大家简单讲解一下：
//这里使用`&`运算将`int`值的最后`7`位取出
byte i = (byte) (iv & 0x7f);
//通过位移操作去掉最后7位
iv = iv >> 7;
if (iv > 0) {
//这里通过`|` 运算将·`i`的最高标志位(即第1位)置为`1`
i = (byte) (i | 0x80);
value.add(i);
toByte(value, iv);
} else {
value.add(i);
}
下章预告：【巧用位运算（三）—— 奇技淫巧 Bitmap】
简介： 通过本章代码我们可以发现，变长整型的核心实现基本离不开位运算。现在是不是更进一步体会到了位运算的实用之处。下一章我们会讲一种完全基于位运算实现的数据结构bitmap，以及更加丧心病狂的内存压缩技巧Roaring Bitmaps，敬请大家期待。
2022/10/21 补充
最近在看Hyperledger Fabric的源码时发现在blockfile的blockBytesLen写入时也使用了变长整形的实现：
blockBytesLen := len(blockBytes)
blockBytesEncodedLen := proto.EncodeVarint(uint64(blockBytesLen))
totalBytesToAppend := blockBytesLen + len(blockBytesEncodedLen)
func EncodeVarint(x uint64) []byte {
var buf [maxVarintBytes]byte
var n int
for n = 0; x > 127; n++ {
buf[n] = 0x80 | uint8(x&0x7F)
x >>= 7
}
buf[n] = uint8(x)
n++
return buf[0:n]
}
