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;
}