前言
本文收录于专辑：http://dwz.win/HjK，点击解锁更多数据结构与算法的常识。
你好，我是彤哥，一个每天爬二十六层楼还不忘读源码的硬核男人。
置信大家都有过抢票、刷票的教训，每年年底，这都是一场盛宴。
然而，你有没有想过12306的抢票算法是怎么实现的呢？
没有吧，想过，还是没有脉络？
明天，咱们就来曝光让人又爱又恨的12306是如何实现抢票的。
位运算回顾
咱们晓得计算机只能辨认0和1，要操作这些0和1，只能通过位运算来进行，那么，一共有几种位运算呢？
让咱们来回顾一下：
| 运算 | 符号 | 举例 | 后果 | |
|---|---|---|---|---|
| 与 | & | 1101 & 0110 | 0100 | |
| 或 | \ | 1101 & 0110 | 1111 | |
| 异或 | ^ | 1101 ^ 0110 | 1011 | |
| 取反 | ~ | 1101 | 0010 | |
| 左移 | << | 1101 << 1 | 11010 | |
| 带符号右移（高位补1） | >> | 1101 >> 1 | 1110 | |
| 不带符号右移（高位补0） | >>> | 1101 >>> 1 | 0110 |
以上位运算以Java为例，其余语言中可能没有 >>> 操作。
OK，位运算的简略回顾就到这里，还有不懂的同学能够自行百度一下。
位图
尽管大部分语言都有提供位运算，然而，并没有提供一种相似于位数组的类型，要应用这些位运算，咱们只能通过数字类型来实现，比方Java中的int/long等类型。
而这些数字类型的数组，咱们个别能够称之为“位图”（BitMap）。
比方，咱们须要应用128位的内存，能够申请蕴含两个long类型的数组long[] bitmap = new long[2];。
不过，位图有什么用呢？
有大用处哦，比方，咱们要统计某个用户一年的活跃度，就能够应用位图来实现。
一年有365天，一个long类型能够示意64位，365/64=6，只须要6个long类型就能够记录一个用户一年的沉闷状况，怎么记录呢？
很简略，初始时，位图中所有位都是0，当这个用户某天登录了，就在位图中找到这天，把其位变成1，一年下来，这张位图就记录了这个用户哪些天登录了，统计这个位图中1的数量，除以365，就失去了他的活跃度。
OK，这只是位图的一个很简略的用法，位图还有很多高级的用法，比方统计沉闷用户数、限流、权限管制等，当然，还有咱们明天要曝光的12306抢票算法。
12306抢票算法
咱们晓得，一列火车，有很多个座位，能够到很多站，以北京到广州的一列火车G67为例：
G67次列车一共有18个站，有的人可能到武汉就下车了，有的人可能到长沙下车，还有的人可能从武汉上车从衡山西下车，甚至还有的人从北京始终坐到广州，咱们假如这趟列车一共有200个座位。
那么，如何实现正当的抢票策略，能力保障这趟列车可能坐最多的人？（没有站票）
什么叫做“坐最多的人”呢？假如针对10号地位，一个人从北京到武汉，另一个人从武汉到长沙，再一个人从长沙到广州，那针对这个地位全程能够坐3集体；针对另一个地位，一个人从北京到广州，那这个地位全程只能坐一个人。简略点说，就是针对一个特定的地位，两个人之间不能有交加，比方一个人从北京到长沙，另一个人从武汉到广州，那这两个人不能安顿到同一个地位上。
OK，先给你一分钟工夫思考一下，先别急着往下看哦。
好了，一分钟工夫已到，让咱们持续。
首先，让咱们回顾下G67这趟列车的信息：一共18个站，一共200个座位。
为了不便解说和画图，咱们假如它只有 北京、信阳、武汉、岳阳、长沙、广州 6个站，一共有8个座位。
针对这样的信息，咱们能够这样来实现抢票策略：
- 创立5个位图，每个位图的大小为8位，初始时，每个位的值都是0。
为什么是5个位图呢？因为到站就下车了，而广州站是终点站，到站全副人都得下车。比方，一个人从北京到武汉，他到武汉就下车了，所以，它不会占用武汉的地位。
- 把抢票逻辑放在单线程中来解决，单线程的益处是不必思考并发问题，没有CPU上下文切换的问题等，而且整个操作都是CPU操作，速度很快，应用单线程效率更高。
当然，咱们还有更好的抉择——Redis，Redis自身就是单线程解决的，而且它人造反对BitMap，速度又快又好，有趣味的同学能够理解一下Redis中的BitMap。
- 假如第一个人的申请过去了，他要抢从北京到武汉的票，此时，咱们只须要把北京和信阳两个位图做“与”运算，后果中，所有0的地位都示意可抢的地位，在这些地位中随机返回一个即可，并把此地位在北京和信阳这两个位图中标记为1，示意此地位在北京和信阳有人占用了。（武汉为什么不参加运算了，后面讲过了，这个人到武汉就下车了。）
假如，此人最初的座位是2号，那么运算之后，各位图的状况如下：
- 接着，第二个人的申请过去了，假如他要从信阳到长沙，此时，须要把信阳、武汉和岳阳三个位图做“与”运算：
假如，此人最初的座位是4号，那么，运算之后，各位图的状况如下：
- 而后，第三个人的申请来了，假如他要从北京到广州，此时，把所有5个位图做“与”运算：
假如，此人最初的座位是1号位，那么，运算之后，各位图的状况如下：
- OK，通过了多集体的申请之后，假如位图的状况变成了上面这样：
请思考，此时，还能抢到从北京到广州的票吗？
能？不能？答复能的同学，请从头再看一遍^^
好了，对于抢票算法咱们就介绍到这里，你有没有Get到呢？或者你有没有更好的实现办法呢？
后记
本节，咱们一起重温了位运算的操作，并学习了如何应用位图实现12306的抢票算法，对于位图，其实还有很多用处，比方，各种统计、限流、权限管制等。
彤哥收到最新情报：所有的递归都能够改写成非递归，怎么实现呢？有没有什么套路呢？下一节，咱们一起来聊下这个话题。
关注公号主“彤哥读源码”，解锁更多源码、根底、架构常识。