1.首先想到的就是通过与运算获取
public static int bitCount(long i) {
// HD, Figure 5-14
i = i - ((i >>> 1) & 0x5555555555555555L);
i = (i & 0x3333333333333333L) + ((i >>> 2) & 0x3333333333333333L);
i = (i + (i >>> 4)) & 0x0f0f0f0f0f0f0f0fL;
i = i + (i >>> 8);
i = i + (i >>> 16);
i = i + (i >>> 32);
return (int)i & 0x7f;
}
这个方法是java提供的一个计算的方式。
那么问题来了。这样计算是可以的，也很快。但是我想更快怎么？
2.通过缓存的方式来出来
为了更快的速度，那我们可以牺牲一部分存储空间。就是最典型的 空间换时间
我们可以生成一个key-value的接口对应起来
1 -> 1 -> 1
2 -> 10 -> 1
3 -> 11 -> 2
4 -> 100 -> 1
5 -> 101 -> 2
6 -> 110 -> 2
7 -> 111 -> 3
8 -> 1000 -> 1
我们稍微计算一下啊
int 有4字节，32位范围
-2147483648—2147483647(2^31-1)
我们只要计算一下大概有多少
先算正整数。
我们只要计算一下大概有多少
我们估算位2^32这些数据
共占有2^34个字节
1个int 占用2^2个字节
1Gb = 2^30 B
大概约等于4G的空间这是key，要是K-V的方式存放，远远大于额8G
有没有方式优化存储方式？
1.对数据进行降维打击
我们可以吧K-V的方式转换成二维平面，对k-v求解向量。我们就得到的了一个点。这样存的数据远远小于4G
。甚至也就只有1G左右。但是不够我还想更小。
2.考虑拆分法
int ：4个字节 32位
可以拆成 16位 + 16位
拿的key的存放应该是2^5MB
那么肯定有小伙伴会问如果我们分成
8位 + 8位 + 8位 + 8位
是不是更小。
我们如何判断那个一更好？是16位还是8位？
这就涉及到CPU的寄存器。
最好的方式就是分的位数和寄存器的位数一样大。这样速度是最快的。
