Problem Solving►UVa

UVa 128 - Software CRC

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址
中文網址

每一個 ASCII 字元就代表了一位數(8-bit)，而 CRC 值則是加在 LSB 後的 16-bit，使得此數可被 G 整除。
注意輸入如為空(只有End of line)，輸出應為 00 00 。

Solution

先做大數 mod，邊乘邊 mod。
接著為了要計算 CRC 值，需要先將數字向左移 16 位，分兩次來做，防止溢位。
(((now << 8) % G) << 8) % G 可得到餘數，再用 G 減掉它即可得到要加上去的 16-bit 了。

輸出格式需分成兩個部分，now >> 8 移完剩下的就是前 8 位了。 now % 256 則是後 8 位。

Code

UVa 128
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<cstdio>
#define G 34943

int main()
{
    char num[1025];

    while (gets(num) && num[0] != '#')
    {
        if (!num[0])
            puts("00 00");
        else
        {
            int now = 0;
            for (int i = 0; num[i]; i++)
                now = ((now << 8) + num[i]) % G;
            now = G - (((now << 8) % G) << 8) % G;
            printf("%02X %02X\n", now >> 8, now & 255);//now & 255 = now & ((1<<8)-1) = now % 256
        }
    }

    return 0;
}