【大厂机试题解法笔记】报文响应时间

题目

IGMP 协议中，有一个字段称作最大响应时间 (Max Response Time) ，HOST收到查询报文，解折出 MaxResponseTime 字段后，需要在 (0，MaxResponseTime] 时间 (s) 内选取随机时间回应一个响应报文，如果在随机时间内收到一个新的查询报文，则会根据两者时间的大小，选取小的一方刷新回应时间。

最大响应时间有如下计算方式：
当 Max Resp Code < 128, Max Resp Time = Max Resp Code；
当 Max Resp Code ≥ 128,

Max Resp Time = (mant | 0x10) << (exp + 3)；
注: exp最大响应时间的高5~7位: mant 为最大响应时间的低4位。

其中接收到的MaxRespCode 最大值为 255，以上出现所有字段均为无符号数。

现在我们认为 HOST收到查询报文时，选取的随机时间必定为最大值，现给出 HOST 收到查询报文个数 C，HOST 收到该报文的时间T，以及查询报文的最大响应时间字段值 M，请计算出HOST 发送响应报文的时间。

输入描述

第一行为查询报文个数 C，后续每行分别为 HOST 收到报文时间 T 及最大响应时间M，以空格分割。

输出描述

HOST发送响应报文的时间。

备注
用例确定只会发送一个响应报文，不存在计时结束后依然收到查询报文的情况。

用例

输入	输出	说明
3 0 20 1 10 8 20	11	第0秒收到报文，响应时间为20秒（0+20=20）。第1秒收到新报文，响应时间为1+10=11秒，因11<20，更新最小时间为11秒。第8秒收到报文，响应时间为8+20=28秒，维持最小时间11秒。最终结果为11秒

思路

题目核心在考察二进制操作和各进制互转。主要关注 Max Resp Code ≥ 128 时怎么把响应码转成响应时间。mant 是响应码低四位，怎么提取二进制的低四位？提取低四位应该是保留低四位的01状态，把其它位的状态值都置为0，那么与（&）上只有低四位是1其它位是0的二进制数不就保留了第四位，即 mant = code & 0b00001111（0b开头是JavaScript表示二进制字面量的一种写法）,为了代码写起来简洁，一般不直接用二进制字面量，0b00001111可以被看成掩码，转成十进制或十六进制不影响二进制运算。JavaScript 把二进制转十进制需先调用变量toString(radix)方法转为字符串，radix是进制，默认是10，再解析为数字。let b = 0b00001111, decimal = Number(b.toString()) = 15，转为16进制为 hex = toString(16) = 'f'，写成十六进制为 0xf 或0x0f，0x0f 是推荐十六进制字面量写法，它包含了前导0，0x0f 能清晰地表示低 4 位为 1111，高 4 位为 0000，即二进制的 00001111。JavaScript 没法通过函数输出数值类型0x0f 或 0xf 形式的十六进制，只能用字符串表示，JavaScript数值表示一般都是十进制。代码里这样写吧：mant = code & 15。接下来提取exp，图片中显示exp位于第5到第7位之间包含边界，八位二进制从右边第一位起计数，索引按1开始。那么提取高5~7位可以用高5~7位的状态位都是1其余位都是0的二进制数0b01110000进行与操作，然后右移动4位把其余位冲掉，为什么要右移呢，根据题意用掩码提取二进制中的某个部分是用它表示一个新数的，低位的0是丢弃的，故要右移把提取的部分挪到最低位。0b01110000对应十进制是112，所以 exp = code & 112，如果嫌十进制表示的112有点大，可以用十六进制0x70。有了 mant 和 exp 就可以根据公式 Max Resp Time = (mant | 0x10) << (exp + 3) 计算最大响应时间了。

参考代码


function solution() {const C = parseInt(readline());const calculateMPT = function(code) {if (code < 128) return code;const mant = code & 15;const exp = code & 112 >> 4;return (mant | 0x10) << (exp + 3);}let result = Infinity;for (let i = 0; i < C; i++) {const [T, M] = readline().split(' ').map(Number);let mT =  calculateMPT(M);result = Math.min(result, T + mT);}console.log(result);
}const cases = [`3
0 20
1 10
8 20`,
`2
0 255
200 60`
];let caseIndex = 0;
let lineIndex = 0;const readline = (function () {let lines = [];return function () {if (lineIndex === 0) {lines = cases[caseIndex].trim().split("\n").map((line) => line.trim());}return lines[lineIndex++];};
})();cases.forEach((_, i) => {caseIndex = i;lineIndex = 0;solution();
});