位运算（Java实现BitMap）
位运算（Java实现BitMap）
前言：这是第三次写位运算的文章的。昨天线上笔试，对方公司发了一个world文档，题目是这样：
已有一个存储了百万条座机号码的ArrayList，要求写一个方法，返回有序和去重的集合。要求至少两种实现，性能优先。
我想着，你为什么不直接用TreeSet？对于“0133-3023978”，“9764-8977878”这样的字符串，直接用TreeSet还不用自己额外实现sort方法。虽然我不能理解他为什么要用ArrayList，不过我也搞不懂他要求的性能要先到底要怎么优。
我当时计算了下，如果用long（注：将座机号码的连接符“-”删除，就是一个11位的long类型整数），那么最多1千万的数据量，也就80M内存不到（8 * 1000 * 10000/1024/1024M）。
第一种方式：我直接用的TreeSet的构造方法，把ArrayList传递进去。
第二种方式：之前有了解过Redis的BitMap类型，想用该方式实现。但是昨天就不在状态。出去吃了个晚饭，回来才发现这个笔试要求我1个小时内将world文档重新发回对方邮箱。(⊙o⊙)…
开始正文：
BitMap：定义一个足够长的数组，数组的下标代表具体的某个数据，该下标所存储的值用1和0表示是否存在，一个1或0占用1bit，即使从0到1亿，也就是定义new bit[1亿]，占用12M内存。
最开始的时候，我脑袋有点昏，想着一千万个最大一千亿的数字（注：百万级，电话号码11位）用BitMap应该怎么设计和存储，以及Java没有bit这个类，如何使用其他byte或long来代替bit。
当时我犯蠢的时候是这样想的（主要是有点饿得厉害，头已经开始晕了。）
定义一千亿个长度的bit数组，当时我想着，怎么不对劲，怎么需要12G内存，大那么多。而且一千万的数量，我定义一千亿长度，结果只用了一千万个下标，就用了万分之一啊，绝对有什么问题。
实际上是我没能完全理解BitMap的问题
网络上很多博客都直接是这样描述的：对10亿个数字去重和排序
他们只提到了数据量，却没有说这10亿个数字都是什么数字，他们直接简单的把10亿个数字理解成0-10亿。
如果你没有正确理解这点，想当然的顺着他们的思路直接用BitMap存储一千亿个索引，那么当然内存会溢出。
实际上，可以以10亿为标准进行判断，按照BitMap，10亿最大数值，需要用10亿的length的bit数组，也就是120M内存占用。
使用Java来实现BitMap：
1M=1024KB；1KB=1024Byte； 1Byte=8bit
一个int占4Byte，long占8byte。基本类型的所占存储空间的大小并不随机器硬件架构的变化而变化，boolean类型所占存储空间的大小没有明确指定，仅定义为能够取字面值true或false。
题目：有随机生成10亿的0-10亿大小的正整数，请使用Java实现BitMap进行去重和排序
@Slf4j
public class BitMap {
final List<Integer> randomNumberList;
byte[] bitMap;
static char[] charNegative128 = new char[]{'1', '0', '0', '0', '0', '0', '0', '0'};
public BitMap(List<Integer> randomNumberList) {
this.randomNumberList = randomNumberList;
bitMap = new byte[10000 * 10000 * 10 / Byte.SIZE];
}
/**
* Integer.MAX_VALUE是2147483647,21亿
*/
public void addAll() {
/*
由于是10亿个数字，可以优化下
int index = number / 8;
int bitOffset = number % 8;
*/
for (Integer number : randomNumberList) {
int index = number >> 3;
int bitOffset = number & 0x7;
// 这里比较特殊，余0是00000001，余1是00000010，因为一共是8位，但是余数只有7，为了统一减少运算步骤，将余0划分给一个1
bitMap[index] |= 1 << bitOffset;
log.debug("number: " + number + "index: " + index + "bitOffset: " + bitOffset + "bitMap[i]" + bitMap[index]);
}
}
public List<Integer> getAll() {
addAll();
List<Integer> numberList = new ArrayList<>();
for (int i = 0; i < bitMap.length; i++) {
if (bitMap[i] != 0) {
char[] bitOffsets = bitMap[i] == - 128 ? charNegative128 : Integer.toBinaryString(bitMap[i]).toCharArray();;
log.debug(Arrays.toString(bitOffsets));
for (int j = 0; j < bitOffsets.length; j++) {
if (bitOffsets[j] == '1') {
log.debug("index: " + i + " bitOffset: " + (bitOffsets.length - j));
numberList.add(i << 3 | (bitOffsets.length - j - 1));
}
}
}
}
return numberList;
}
public static void main(String[] args) {
// BitMap bitMap = new BitMap(Arrays.asList(359395975));
// List<Integer> all = bitMap.getAll();
// all.forEach(System.out::println);
// 特殊：byte的1<<7是负数，因为符号位是1了，使用Integer.toBinaryString（）时会返回32位
byte testByte = (byte) (1 << 7);
System.out.println(testByte);
System.out.println(1 << 7);
// Byte.MIN_VALUE
List<Integer> randomNumberList = new ArrayList<>();
Random random = new Random();
for (int i = 0; i < 10; i++) {
randomNumberList.add(random.nextInt(10000 * 10000 * 10));
}
Collections.sort(randomNumberList);
BitMap bitMap = new BitMap(randomNumberList);
List<Integer> allNumberList = bitMap.getAll();
for (int i = 0; i < randomNumberList.size(); i++) {
System.out.println(randomNumberList.get(i) + "\t" + allNumberList.get(i));
}
}
}
下面讲下移位运算，也是本文主要的内容。因为我老是对三个移位运算有点乱。
计算机中存储的数字的二进制都是以
补码的形式存储的，位运算的时候也是使用的补码。而读取显示成我们常用的基本类型则是又转换为源码
正数：原码的最高位，即符号位为0，原码=反码=补码
负数：原码的最高位，即符号位为1。
负数的原码可以看做在正数的原码基础上，将符号位由0改为1；
负数的反码：负数的原码，除符号位，其他位取反。
负数的补码：在负数的反码的最低位+1。
左移只有一种：<<。因为左移之后，一律在低位补0，和符号无关（注：低位是右边，高位是左边。和普通的数字一样理解高低位即可）。
右移有两种：>>和>>>。>>是有符号右移，>>>是无符号右移。
有符号右移>>，在高位根据符号位补入和符号位标识，即负数>>，则高位补入1；正数>>，则高位补入0；
无符号右移>>>，使用“零拓展”，在高位补入0。
移位运算分成正负数来分别记录比较好理解（以下，假定移位运算结束后，结果没有溢出）。
有正整数x，移位n，那么x<<n = x * 2^n；x>>n = x >>> n = x / 2^n
有负整数x，移位n，x<<n没有什么规律，得根据实际数字进行判断；x>>n=x/2^n；x>>>n变为正数，结果值根据实际情况判断。
位运算的>>相当于做除法，他的除法和java的直接使用/稍微有些不一致。Java的/是直接截断小数部分，位运算的>>是将低位的1抹去了，这在负数时两种情况是不一致的，稍微有点差别。
| number | >>1 | Java(/2) |
|---|---|---|
| 3 | 1 | 1 |
| -3 | -2 | -1 |
其他位运算：
1.与（&）：11得1，10得0，00得0.
2.或（|）：11得1，10得1，00得0.
3.异或（^）：11得0，10得1，00得0（异或、异或、不一样了才或，一样就直接为0，相同为0，不同为1）.
4.非（~）：这是一元运算符，上面3个是2元运算符，0得1，1得0（取反）。
为什么计算机中符号位用0代表正数，用1代表负数？
按照正常理解来说，1代表存在，应该是表示正数才对，相应的0才应该用来代表负数。
一个结论如果想要推导他是正确的，那么可以找到很多个理由。你自己找一个能让自己同意的说法就好。
为什么要使用补码来进行计算？
事物的发展规律都是：先有需求然后创造，再根据实际情况想办法优化。
而补码就肯定是一种优化手段，那它解决和优化了什么呢？
废话：根据只有负数的反码和补码和源码不一致，而正数则没有变化这一情况来看，并且运算都是使用补码计算，而补码则是在反码基础上+1，那么这个1就有大用，并且是先出现的反码再出现补码，那么反码应该解决了一部分问题但是没有完全解决，导致计算的时候需要用1来进行补足。
结果：在规定了符号位0代表正数，1代表负数的情况下：使用源码进行正负数相加，由于符号位参与运算，结果肯定不正确；然后探索出给负数进行补码，这样子解决了小数-大数，但是大数-小数结果始终相差1；最后探索出负数使用补码。（注：减去一个数相当于加上这个数的负数）