推 puzi:這跟我要這星期交的作業好像喔！ 11/02 15:31
※ 引述《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