ZJU-199001 第三周练习 2 数字特征值 位运算算法

• 2022 年 8 月 27 日
• 筆記
• C/C++

题目

对数字求特征值是常用的编码算法,奇偶特征是一种简单的特征值. 对于一个整数, 从个位开始对每一位数字编号, 个位是 \(1\) 号, 十位是 \(2\) 号, 以此类推. 这个整数在第位上的数字记作 \(x\), 如果 \(x\) 和 \(n\) 的奇偶性相同, 则记下一个 \(1\), 否则记下一个 \(0\). 按照整数的顺序把对应位的表示奇偶性的 \(0\) 和 \(1\) 都记录下来, 就形成了一个二进制数字. 比如, 对于 \(342315\), 这个二进制数字就是 \(001101\).

代码

#include <stdio.h>

int main() {
    int n;
    scanf_s("%d", &n);

    int e = 0;
    for (int i = 0; n; i++) {
        e ^= (n + i & 1) << i;
        n /= 10;
    }

    printf("%d", e);

    return 0;
}

解析

要获取一个数字 \(x\) 第 \(n\) 位的奇偶, 只需要除以 \(10^{n-1}\). int 的特性将使结果向下取整, 例如: \(342315/10^1=34231\), 我们仅需要关注结果的个位数即可. 同时, 奇偶性相同的数字相加, 结果为偶数; 反之为奇数. 计 \(x\) 从左数第一位到右数第 \(n\) 位, 与数位相加, 即可分析奇偶性.

此处, 我们有两种判断奇偶的方法:

1. 使用整除运算符 %, 偶数结果为 0.
2. 与 1 进行按位与操作 (原理见此处), 偶数结果为 0. 本代码使用此种算法.

Tip: 加和结果为偶数时结果为 1 会更方便, 因此 for 循环中的 i 从 0 开始计数.

我们知道, 位运算中的左移的效果是乘二, 因此, 我们将上述过程中得到的 0 或 1 进行左移, 偏移量即目前所在的数位. 如此, 我们不必再去调用 pow() 函数.

当然, 你也可以设置一个值 pow2, 在每次循环末翻倍, 加上之前提到的整除法判断奇偶, 你的代码大致如下.

int e = 0;
int pow2 = 1;
for (int i = 0; n; i++) {
    e ^= (n + i) % 2 * pow2;
    n /= 10;
    pow2 *= 2;
}