เพิ่มค่า Unsigned Number โดย Swap บิตตำแหน่งปลายใน C++

โจทย์

ได้รับตัวเลข เพิ่มค่าโดยการ Swap บิตที่ตำแหน่งปลาย คือ ตำแหน่งแรกและสุดท้าย ตำแหน่งที่สองและสองจากท้าย และต่อไป

ถ้าตัวเลขอินพุตคือ 8 Binary Representation คือ

00000000 00000000 00000000 00001000

หลัง Swap บิตตำแหน่งปลาย ตัวเลขกลายเป็น

00010000 00000000 00000000 00000000 และค่า Decimal คือ: 268435456

อัลกอริทึม

1. สร้าง Copy ของตัวเลขต้นฉบับ
2. ถ้า Less Significant Bit เป็น 1 และ More Significant Bit เป็น 0 ให้ Swap บิตในตัวเลขผลลัพธ์เท่านั้น ทำต่อจนกว่า ตำแหน่ง LSB จะไม่ต่ำกว่า MSB
3. คืนตัวเลขใหม่

ตัวอย่างโค้ด

#include <bits/stdc++.h>
#define ull unsigned long long
using namespace std;

ull getMaxNumber(ull num) {
    ull origNum = num;
    int bitCnt = sizeof(ull) * 8 - 1;
    int cnt = 0;
    for (cnt = 0; cnt < bitCnt; ++cnt, --bitCnt) {
        int m = (origNum >> cnt) & 1;
        int n = (origNum >> bitCnt) & 1;
        if (m > n) {
            int x = (1 << cnt | 1 << bitCnt);
            num = num ^ x;
        }
    }
    return num;
}

int main() {
    ull num = 8;
    cout << "Maximum number = " << getMaxNumber(num) << endl;
    return 0;
}

ผลลัพธ์

Maximum number = 268435456