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

题目

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

代码

#include 

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" role="presentation">x$x$ 第 n" role="presentation">n$n$ 位的奇偶, 只需要除以 10n−1" role="presentation">10n−1${10}^{n-1}$. int 的特性将使结果向下取整, 例如: 342315/101=34231" role="presentation">342315/101=34231$342315/{10}^1=34231$, 我们仅需要关注结果的个位数即可. 同时, 奇偶性相同的数字相加, 结果为偶数; 反之为奇数. 计 x" role="presentation">x$x$ 从左数第一位到右数第 n" role="presentation">n$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;
}