位运算应用实例

数据结构与算法

---

二进制基础

十进制与二进制的转换

10换2要诀：除二取余，然后倒序排列，高位补零

例如：十进制52换算结果为110100

2换10要诀：

2换10要诀：从低位（右边）算起位置下标为n，2的a幂次方 乘以二进制对应位的数值a[0或1]，再求各个位之和，公式为（暂时写不出）：

$$\sum_{i=0}^n a_i= 2 ^n-1$$

例如：二进制110换算结果为6

$$(2^2 * 1) + (2^1 * 1) + (2^0 * 0) = 4 + 2 + 0 = 6$$

---

位运算

运算符	含义	功能
&	按位与	如果两个相应的二进制位都为１，则该位的结果值为１；否则为０。
|	按位或	两个相应的二进制位中只要有一个为１，该位的结果值为１。
∧	按位异或	若参加运算的两个二进制位同号则结果为０（假）异号则结果为１（真）
～	取反	～是一个单目（元）运算符，用来对一个二进制数按位取反，即将０变１，将１变０。
<<	左移	左移运算符是用来将一个数的各二进制位全部左移N位，右补０。
>>	右移	表示将a的各二进制位右移N位，移到右端的低位被舍弃,对无符号数,高位补0。

与&运算
样本数1	111【7】	111【7】	1000【8】
样本数2	010【2】	101【5】	0101【5】
操作结果	010【2】	101【5】	0000【0】

或|运算
样本数1	111【7】	111【7】	1000【8】
样本数2	010【2】	101【5】	0101【5】
操作结果	111【7】	111【7】	1101【13】

或>>运算
样本数a	11111【31】	111【7】	100000【32】
操作	>>2	>>2	>>2
结果	00111【7】	001【1】	1000【8】

PS：对于二进制的学习建议是：时刻参考0到7的二进制数值；对熟识规律、分析逻辑有大帮助
000【0】
001【1】
010【2】
011【3】
100【4】
101【5】
110【6】
111【7】

---

应用例子

1、奇偶数判断

常见做法对2取余：

if(value % 2 == 0){
   return true;
}
return false;

如果操作数value是小数的话，还勉强行得通，但是value是一个上百万的大数，那么这就白白浪费了CPU的大量时间，程序的效率和性能就很差。回头观察0至7二进制对照表，可以发现规律：偶数二进制个位数恒为0，而奇数个位数恒为0。而通过与运算可得推论：

任意偶数 & 1 = 0
任意奇数 & 1 = 1

对2取余方法可以改为：

if(value & 1 == 0){
   return true;
}
return false;

---

2、记录海量热数据状态

从Redis 2.2开始，Redis提供了GETRANGE/SETRANGE/GETBIT/SETBIT四个用于字符串类型Key/Value的命令。通过这些命令，我们便可以像操作数组那样来访问String类型的值数据了。比如唯一标识用户身份的ID，可能仅仅是String值的其中一段子字符串。这样就可以通过GETRANGE/SETRANGE命令来方便的提取。再有就是可以使用BITMAP来表示用户某天的是否登录状态，如1表示有登录，0表示没登录。用这种方式来表示100,000,000个用户的时，也仅仅占用12MB的存储空间，与此同时，在通过SETBIT/GETBIT命令进行数据遍历也是非常高效的。

实测Redis插入100,000,000位Bitmap，占用内存如下：

# Memory
used_memory:14389312
used_memory_human:13.72M
used_memory_rss:14389312
used_memory_peak:14457332
used_memory_peak_human:13.79M
used_memory_lua:31744
mem_allocator:libc

---

3、快速去重排序

利用JDK方法实现整数去重排序方法，JDK7以后默认排序方法为Timsort，本质是二分法插入排序与归并排序的结合，时间复杂度是O(n log n)；以下实现例子不考虑利用Map进行去重。

    private static List<Integer> fnJDKSort(Integer[] arr) {
        //首先利用Stream.distinct()进行去重，暂时不考虑用Set接口
        List<Integer> list = Arrays.asList(arr).stream().distinct().collect(Collectors.toList());
        //再排序
        Collections.sort(list, new Comparator<Integer>() {
            public int compare(Integer o1, Integer o2) { if (o2 > o1) { return -1; } return 1；}
        });
        return list;
    }

无论何种排序算法，都会涉及元素之间的比较动作；而反观位图，由于位图的数据结构，位图具有的以下两点特性可以帮助实现无需通过元素比较，时间复杂度为O(1)的排序方法：

1. 快速随机访问位
2. 位的有序性

实现步骤：
第一阶段将所有的位都置为0，从而将集合初始化为空；
第二阶段通过读入随机集合的每个整数来建立集合，将每个对应的位都置为1；
第三阶段检验每一位，如果该位为1，就输出对应的整数，由此产生有序的输出结果。

    private static List<Integer> fnBitSet(Integer[] arr) {
        final BitSet bitSet = new BitSet();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            bitSet.set(arr[i], true);
        }
        for (int i = 0; i < arr.length; i++) {
            if (bitSet.get(i)) {
                list.add(i);
            }
        }
        return list;
    }

两种方法性能耗时对比：

样本量	Sort(ms)	BitMap（ms）
1000，1千	80	1
10000，1万	165	4
100000，10万	180	20
1000000，100万	530	120

---

4、分组运算

分组运算：根据某个或多个特征值对数据集合进行划分分组，目标是提升数据访问与存储效率。常见应用场景：

1. 数据库分片
2. Hash散列位置下标计算
3. 业务逻辑随机分组

Hash散列的数据结构是通过数组与链表的组合（链表的数组集），通过对象的散列码定位对象在数组中的位置下标，同一位置下标的多个对象，则以链表形式存储，因此，如何利用对象的散列码可以均匀定位到数组不同位置中，减少由于冲突而生成链表，是Hash散列函数的关键算法。

Hashtable采用最常见算法有除留余数法，而HashMap则通过效率更高更巧妙位运算法，同样实现了均匀的散列。关于除留余数法更多分析以及两种算法的优劣对比参考：散列函数设计：除留余数法，但余数法并非本文讨论重点，留待更多实验与讨论。

HashMap位算法非常简单：数组位置下标 = 散列码 & (数组长度 - 1)。参考源码：

int n = (tab = resize()).length; //Hash数组长度
Node<K,V> p  = tab[i = (n - 1) & hash];

当HashMap初始化时，数组默认长度为16，运算公式为：16-1 & hash，参考以下示例：

散列码	运算	结果
10001101【141】	1111 & 10001101	1101【13】
10001110【142】	1111 & 10001110	1110【14】
10001111【143】	1111 & 10001111	1111【15】
10010000【144】	1111 & 10010000	0000【0】
10010001【145】	1111 & 10010001	0000【1】

巧妙之处在于以下两点：

1、根据HashMap的设计，其数组的长度length必然为2的整数次幂，确保了length - 1为奇数，奇数的二进制最后一位尾数必为1，所以散列码的最后一位无论是1或是0，与运算结果都会产生1或0的结果。反之，如果Length为偶数，尾数是0，与运算结果只可能是0。导致所有位置索引的计算值都只能是偶数，浪费一半空间。

2的整数次幂		2的整数次幂-1
$$2^1 = 2$$	10	$$2^1 -1= 1$$	1
$$2^2 = 4$$	100	$$2^2 -1= 3$$	11
$$2^3 = 8$$	1000	$$2^3 -1= 7$$	111
$$2^4 = 16$$	10000	$$2^4 -1= 15$$	1111
$$2^5 = 32$$	100000	$$2^5 -1= 31$$	11111
...	...	...

2、 通过与运算索引，一次运算效率更高，而且保证取样数据小于table长度，例如，长度为16（10000），length - 1 = 15（1111）；所有与15参与运算的Hash，实际运算都只有后4位，必然不会产生大于15的值

---

5、灵活高效状态存储

案例A：在运营系统中，用户可以领取现金券20、30、50...元，按照传统关系型数据库设计，需要一张领取记录表，记录用户编号及每张现金券的领取状态。前台查询用户是否已经领取指定面额现金券，则需要查询：
select 状态 from Record where 用户ID = id and 面额 = amount

用户ID	面额	状态
148	20	领取
148	30	领取
148	50	未领取
233	20	未领取
233	30	领取
233	50	领取
...	...	...

如果换成bitmap存储怎么玩？根据需求，用户可领的现金券面额是有限的，首先按序，为每张面额的券分别指定一个十进制整数标识码，如下表：

面额	标识码
20	1【1】
30	10【2】
50	100【4】
..	1000【8】
..	10000【16】
..	100000【32】

标识码计算公式是：

$$2 ^ n$$

而用户的领取状态则为已领券面额对应标识码之和：

$$\sum_{i=0}^n a_i= 2 ^n + ... + 2^1 + 2^0$$

回到案例，根据领取记录表可知：148用户已领取20、30元，标识码分别为1、2；233用户已领取30、50元，标识码为：2、4。

用户ID	领券状态
148	3 = 1 + 2
233	4 = 2 + 4

当需要查询用户领券状态时，语句则改为：select 1 from Record where 用户ID = id and 领券状态 & amount = amount。例如148用户，3 & 2 = 2表示已经领取30元，而3 & 5 = 0则表示用户还没领取50元。

转码	标识码	低位下标
1	【1】	0
10	【2】	1
100	【4】	2
1000	【8】	3
10000	【16】	4
100000	【32】	5

根据面额与标识码的映射表，标识码转换为二进制后，所有转码的最高位都是1，其他位数均为0，且各不相等，因此转码之和一定不会发生进位。例如：标识码是21 = 1 + 4 + 16，转码结果就是10101 = 10000 + 100 + 1 。

由于0与无论是0或1进行&运算，结果都是0；因此只要总和 & 标识码 = 标识码，表示总和包含对应标识码。十进制公式为：

$$(2^a + 2^b) \& 2^a = 2^a [a!=b]$$

10101 &
10000 =
10000 //21包含16
10101 &
01000 =
00000 //21不包含8

---