很多编程语言都有位运算符,Java语言也不例外。在Java语言中,提供了7种位运算符,分别是按位与(&)、按位或(|)、按位异或(^)、取反(~)、左移(<<)、带符号右移(>>)和无符号右移(>>>)。
这些运算符当中,仅有~是单目运算符,其他运算符均为双目运算符。
在讲解这些运算符的使用之前,必须了解一个常识,那就是:位运算符是对long、int、short、byte和char这5种类型的数据进行运算的,我们不能对double、float和boolean进行位运算操作。
如果你要理解本文章的理论和逻辑,可以参考,有人写了我就不啰嗦了
全网首发:12306抢票算法大曝光?(十张图搞定)
https://segmentfault.com/a/1190000023534009
如果你对Redis位图不理解,可以参考
使用Bitmaps位图实现Redis签到
https://www.javacui.com/DB/703.html
其他知识内容可以参考
https://www.javacui.com/index.php?keyword=redis
如果你已经了解运算符和Redis位图,那么按照上面文章说法,逻辑其实很简单,就是把所有座位初始化为位图,当你购买车站A到车站B的票时,把中间车站的位图进行计算,如果最终计算有票,则为有票。
当然这边只是在技术上对于这个逻辑进行了实现,12306实际的逻辑的话,大家都懂的,天花板。
相关逻辑的解释,都在注释里面了,直接运行一下即可理解,上代码:
package com.example.springboot; import org.junit.jupiter.api.Test; import org.springframework.beans.factory.annotation.Autowired; import org.springframework.boot.test.context.SpringBootTest; import org.springframework.data.redis.connection.BitFieldSubCommands; import org.springframework.data.redis.core.RedisTemplate; import java.util.ArrayList; import java.util.List; /** * 12306分段购票模拟 */ @SpringBootTest public class A12306 { @Autowired private RedisTemplate redisTemplate; private final static int cz = 5; // 几个站点 private final static int zw = 5; // 几个坐位 @Test public void test1() { init(); // 购买 2 张 1-3的票,此时有票 int from = 1, to = 3; for (int i = 0; i < 2; i++) { qp(from, to); } from = 2; to = 4; // 购买 2 张 2-4的票,此时有票 for (int i = 0; i < 2; i++) { qp(from, to); } from = 1; to = 5; // 购买 2 张 1-5的票,此时有 1 张票 for (int i = 0; i < 2; i++) { qp(from, to); } from = 1; to = 3; // 购买 1 张 1-3的票,此时 无票 qp(from, to); } public void qp(int from, int to) { System.out.println("=========================== 购票开始 ==========================="); // 这里是要购买的起始站到终点站中间所有站的坐位情况 List<Long> czLong = new ArrayList<>(); // 最后一站 不用取,因为最后一站下车,下车就可以继续从这站开始买 for (int i = from; i < to; i++) { // 这里取的时候要多取一个,因为 0 位是默认的 1 List<Long> list1 = redisTemplate.opsForValue().bitField(i + "", BitFieldSubCommands.create().get(BitFieldSubCommands.BitFieldType.unsigned(zw + 1)).valueAt(0)); long temp = list1.get(0); System.out.println("车站 " + i + " 购票前 坐位情况 " + Long.toBinaryString(temp)); czLong.add(temp); } long v = 0; for (Long l : czLong) { // 两个都为 0 时,才为 0 v = v | l; } // 转为 2 进制 01 的字符串 String b = Long.toBinaryString(v); System.out.println("最终计算 坐位情况 " + b); // 如果最终结算里面包含 0 ,说明有坐位,可以购买 if (b.indexOf("0") > -1) { // 1 代表无票,把无票的去掉,长度就是总票量 b = b.replace("1", ""); System.out.print(from + " 到 " + to + " 有票 总票量 " + b.length()); // 坐位,这里从右边开始取,否则无法进行下面的运算 A: for (int i = zw; i > 0; i--) { // 按位操作向右位移1,再移动回来,再移回来时是用0补位,如果补位后相等说明这个位本来就是0 if (v >> 1 << 1 == v) { System.out.println(" 您的坐位编号:" + i); for (int j = from; j < to; j++) { // j 站点编号 i 坐位号 ,这里要把区间的车站都标为占用 redisTemplate.opsForValue().setBit(j + "", i, true); } break A; } // 是右移后赋值,意思是向右移动一位出去,此时变量v的值将发生变化 v >>= 1; } // 打印购票后所有站坐位情况,最后一站不打印 for (int i = 1; i < cz; i++) { // 这里取的时候要多取一个,因为 0 位是默认的 1 List<Long> list1 = redisTemplate.opsForValue().bitField( i + "", BitFieldSubCommands.create().get(BitFieldSubCommands.BitFieldType.unsigned(zw + 1)).valueAt(0)); long temp = list1.get(0); System.out.println("车站 " + i + " 购票后 坐位情况 " + Long.toBinaryString(temp)); } } else { System.out.println(from + " 到 " + to + " 无票"); } System.out.println("=========================== 购票结束 ==========================="); } /** * 初始化站点和坐位 */ @Test public void init() { for (int z = 1; z <= cz; z++) { redisTemplate.delete(z + ""); } for (int z = 1; z <= cz; z++) { // 这里把 0 位设置为 1,这样出来的数据就是 1000,方便查看 redisTemplate.opsForValue().setBit(z + "", 0, true); for (int i = 1; i <= zw; i++) { redisTemplate.opsForValue().setBit(z + "", i, false); } } System.out.println("数据初始化完毕"); } }
运行以后打印结果如下:
数据初始化完毕 =========================== 购票开始 =========================== 车站 1 购票前 坐位情况 100000 车站 2 购票前 坐位情况 100000 最终计算 坐位情况 100000 1 到 3 有票 总票量 5 您的坐位编号:5 车站 1 购票后 坐位情况 100001 车站 2 购票后 坐位情况 100001 车站 3 购票后 坐位情况 100000 车站 4 购票后 坐位情况 100000 =========================== 购票结束 =========================== =========================== 购票开始 =========================== 车站 1 购票前 坐位情况 100001 车站 2 购票前 坐位情况 100001 最终计算 坐位情况 100001 1 到 3 有票 总票量 4 您的坐位编号:4 车站 1 购票后 坐位情况 100011 车站 2 购票后 坐位情况 100011 车站 3 购票后 坐位情况 100000 车站 4 购票后 坐位情况 100000 =========================== 购票结束 =========================== =========================== 购票开始 =========================== 车站 2 购票前 坐位情况 100011 车站 3 购票前 坐位情况 100000 最终计算 坐位情况 100011 2 到 4 有票 总票量 3 您的坐位编号:3 车站 1 购票后 坐位情况 100011 车站 2 购票后 坐位情况 100111 车站 3 购票后 坐位情况 100100 车站 4 购票后 坐位情况 100000 =========================== 购票结束 =========================== =========================== 购票开始 =========================== 车站 2 购票前 坐位情况 100111 车站 3 购票前 坐位情况 100100 最终计算 坐位情况 100111 2 到 4 有票 总票量 2 您的坐位编号:2 车站 1 购票后 坐位情况 100011 车站 2 购票后 坐位情况 101111 车站 3 购票后 坐位情况 101100 车站 4 购票后 坐位情况 100000 =========================== 购票结束 =========================== =========================== 购票开始 =========================== 车站 1 购票前 坐位情况 100011 车站 2 购票前 坐位情况 101111 车站 3 购票前 坐位情况 101100 车站 4 购票前 坐位情况 100000 最终计算 坐位情况 101111 1 到 5 有票 总票量 1 您的坐位编号:1 车站 1 购票后 坐位情况 110011 车站 2 购票后 坐位情况 111111 车站 3 购票后 坐位情况 111100 车站 4 购票后 坐位情况 110000 =========================== 购票结束 =========================== =========================== 购票开始 =========================== 车站 1 购票前 坐位情况 110011 车站 2 购票前 坐位情况 111111 车站 3 购票前 坐位情况 111100 车站 4 购票前 坐位情况 110000 最终计算 坐位情况 111111 1 到 5 无票 =========================== 购票结束 =========================== =========================== 购票开始 =========================== 车站 1 购票前 坐位情况 110011 车站 2 购票前 坐位情况 111111 最终计算 坐位情况 111111 1 到 3 无票 =========================== 购票结束 ===========================
可以看到,如果你买了中间的站点,那么再买起始站到终点站时,就不能买了。
Java小强
未曾清贫难成人,不经打击老天真。
自古英雄出炼狱,从来富贵入凡尘。
发表评论: