原题地址：郑州轻工业大学在线评测系统

题干

  ZHY 与 LZC 两人因为工作原因经常不在同一个城市，但是他们很不喜欢别人有偷窥他们聊天内容的机会，于是他们决定自己编写一套通信软件。

  现在 ZHY 将每次要传输的数据切分为一组 31 x N（宽 x 高）的二进制数据（每行 31bit，共 N 行），因为数据量较大，所以需要做一些特殊的操作来校验数据在传输过程中是否发生比特变换（某一位上 0 变成 1 或 1 变成 0）。

  现在，ZHY 在这组数据的左边添加一列，上面添加一行，这样就将数据拓展为了 32 x (N + 1)，同时规定：

  • 第一行最高位为无效位（其值不影响任何数据）
  • 第一行中（除最高位外）的每一位用于标记当前列（不包括第一行）中 1 的奇偶数
  • 从第二行开始的每一行的最高位用于标记当前行（不包括其本身）中 1 的奇偶数

  当标识位为 1 时表示该标识对应的行/列上 1 的数量为偶数，否则为奇数。

  按照上述规则，我们可将 1011111_00010011_01101011_10111001（共 31bit 其中下划线为辅助标线，无实际意义）划分为下面这样的二维矩阵：

1
2
                                 | -> | 00100000111011001001010001000110
 1011111000100110110101110111001 | -> | 11011111000100110110101110111001

  同理，我们可将0000000_00000000_00000000_00000000_0000000_00000000_00000000_00000000（共 62bit）划分为：

1
2
3
11111111_11111111_11111111_11111111
10000000_00000000_00000000_00000000
10000000_00000000_00000000_00000000

  然而理想很美好，现实很残酷，ZHY 在编写解码软件时遇到了困难，希望你能够帮他写出核心代码。

输入格式

  每行输入一个整数（范围：-2^31 ~ 2^31 - 1），代表软件接收到的信息，直到读取到 EOF 为止（最少 2 行，最多 1024 行）。

  TJJJ 不忍心看新生被 ZHY 折磨，于是提前处理了一下信息，所以我们可以保证数据中最多只有一个错误比特，且标识位一定没有发生比特翻转。

输出格式

  请你纠正信息中的错误比特，然后将正确的信息以二进制形式输出（每行 31bit）.

样例输入 1

1
2
-1
-2147483647

样例输出 1

1
0000000000000000000000000000000

样例输入 2

1
2
3
1020072082
-1772266360
-714099737

样例输出 2

1
2
0010110010111010101110010001000
1010101011011111011001111100101

提示

  样例1 中的输入转为二进制后为：

1
2
11111111111111111111111111111111
10000000000000000000000000000000

  样例2 中的输入转为二进制后为：

1
2
3
00111100110011010001000010010010
10010110010111010101110010001000
11010101011011111011001111100111

题目解释

计算标识位

  这道题题干看起来似乎有点复杂，但是其实原理十分简单。现在，我们先把难度降低一些，假设每行算上校验位一共 8bit，一共 8 行。

  为了方便后续说明坐标，行号从 A 开始计数。

76543210
A*
B1011000
C0001110
D1100011
E0101010
F1010101
G1111111
H1000010

  首先需要注意的是二进制的最右端是最低位，下标从 0 开始从最低位开始向最高位递增。

  从题干中我们不难发现，A7是一个无效位，其值不影响运算，所以我们直接将其忽略。下面我们先把 B 行提取出来演示一下如何计算标识位。

76543210
B1011000

  现在我们数一下这一行中一共有多少个 1，很明显，一共有 3 个，是奇数个，所以标识位应当为 0：

76543210
B01011000

  列的计算方法与行的一样，只不过是竖了过来，这样，我们可以算出其余所有行和列的标识位：

76543210
A*0001000
B01011000
C00001110
D11100011
E00101010
F01010101
G01111111
H11000010

读入数据

  看到输入数据的格式可能又有很多同学蒙圈了——这该怎么读？

  是需要把输入的十进制数转换为二进制吗？很显然不是。如果手动转换为二进制的话我们还需要处理负数补码的问题，我们直接使用位运算就可以处理数字中的二进制信息。

  下面我们说几个常用的位处理方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 获取 data 中下标为 index 的二进制值
// 例如 at(0b00000100, 2) 将返回 1
int at(int data, int index) {
    return (data >> index) & 1;
}

// 反转 data 中下标为 index 的二进制值（0 变 1，1 变 0）
// 例如 not(0b00000100, 2) 将返回 0
int not(int data, int index) {
    return data ^ (1 << index);
}

// 将 data 中下标为 index 的位置设置为 1 并返回
// 例如 setTrue(0b11111101, 1) 将返回 0b11111111
int setTrue(int data, int index) {
    return data | (1 << index);
}

// 将 data 中下标为 index 的位置设置为 0 并返回
// 例如 setFalse(0b11111111, 7) 将返回 0b01111111
int setFalse(int data, int index) {
    return data & ~(1 << index);
}

解题思路

  思路就非常简单了，我们先读入数据，然后计算出所有标识位，再将我们计算的标识位与输入数据中的标识位相对比，找出不一样的行和列就能确定错误位置，反转这个位置的值就是正确结果，如果没有不一样的标识位就说明输入的数据没有错误。

  直接给出代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <stdio.h>

// 输入数据
int input[1024];
// 每行的标识位
int lineTag[1024];
// 每列的标识位，列标从最低位开始从0增长
int columnTag[31];

/** 计算当前数据的第一行校验码 */
void checkColumn(int size) {
    for (int column = 0; column != 31; ++column) {
        columnTag[column] = 1;
        for (int line = 1; line != size; ++line) {
            columnTag[column] ^= (input[line] >> column) & 1;
        }
    }
}

/** 计算当前数据的第一列校验码 */
void checkLine(int size) {
    for (int line = 1; line != size; ++line) {
        lineTag[line] = 1;
        for (int column = 0; column != 31; ++column) {
            lineTag[line] ^= (input[line] >> column) & 1;
        }
    }
}

/** 纠正 */
void correct(int size) {
    checkColumn(size);
    checkLine(size);
    for (int line = 1; line != size; ++line) {
        // 判断输入数据中的行标识和计算出来的行标识是否一致
        if (((input[line] >> 31) & 1) == lineTag[line]) continue;
        // 不一致说明当前行存在错误，遍历列查找错误位置
        for (int column = 0; column != 31; ++column) {
            // 判断输入数据中的列标识和计算出来的是否一致
            // 如果不一致就表示成功定位到错误信息的位置
            if (columnTag[column] == ((input[0] >> column) & 1)) continue;
            // 反转错误信息所在位的值
            input[line] ^= 1 << column;
            return; // 最多只有一个错误，找到后直接退出
        }
    }
}

int main() {
    int size = 0;
    for (int i = 0; ; ++i) {
        if (!~scanf("%d", &input[size])) break;
        ++size;
    }
    correct(size);
    for (int line = 1; line != size; ++line) {
        for (int column = 30; column != -1; --column) {
            printf("%d", (input[line] >> column) & 1);
        }
        printf("\n");
    }
    return 0;
}
创作不易，扫描下方打赏二维码支持一下吧ヾ(≧▽≦*)o