※ 引述《lg31cm (我住5F)》之铭言： : if (crc & 0x8000) : crc = crc << 1 ^ 0x1021; : else : crc = crc << 1; : 手算我已经很熟习,不过看到这段 code 觉得有点神奇,我有把 count 以 1 带入 : 用手算过,跟手算的过程一样,但是用 > 1 带入过程就不一样了,总觉得背後应该 : 有个数学原理可以展开原手算的方法,然後才能写出这样的程式,不知道各位前辈 : 能不能指点一下,thank you! 重点在於这个 (crc << 1)^0x1021 crc&0x8000非0 表示乘上多项式x後出现x^16次项 (因为原式有x^15次项) 而在CRC的计算里 因为是Mod 2 如果出现x^16项一定是1 所以这样的多项式除以x^16+x^12+x^5+1求余就等於原式减去它 在mod 2里减去它又等於对这四项做系数1<-->0的变换 (1-1=0, 0-1=1 (mod 2)) 以binary来说就是xor上0x(1)1021 (binary:(1)0001000000100001) 1 111111 次方: 6 5432109876543210 ↑ x^16项因为是一定要减掉的, 所以就直接让这一位移出去, 就不用xor 而crc&0x8000是0的话表示原式没有x^15项 所以就直接乘上x -- 実琴：「河野！你真的就这样被物质慾望给吸引过去了吗?!」 亨：「只要穿着女装摆出亲切的样子，所有必要花费就能全免，似乎一点都不坏啊。」 実琴：「难道你没有男人的尊严了吗?!」 亨：(断然道)「没有。在节衣缩食且生活吃紧的学生面前，没有那种东西。」 －－プリンセス・プリンセス 第二话 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 192.192.197.112