※ 引述《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