เขียนโปรแกรมกลับบิต (Reverse Bits) ของตัวเลขอย่างมีประสิทธิภาพใน C++

โจทย์

ได้รับ unsigned integer n ต้องการคืนค่าตัวเลขที่ได้จากการกลับลำดับบิตทั้งหมด (reverse bits)

ตัวอย่าง

Input: n = 1 (32-bit)
Output: 2147483648

คำอธิบาย

binary of 1: 00000000 00000000 00000000 00000001
reversed:    10000000 00000000 00000000 00000000 = 2^31 = 2147483648

วิธีที่ 1: Bit-by-bit Check (Straightforward)

#include <iostream>
using namespace std;

unsigned int reverseBitNumber(unsigned int num) {
    unsigned int totalBits = sizeof(num) * 8;  // 32 สำหรับ 32-bit system
    unsigned int reversed = 0;
    
    for (int i = 0; i < totalBits; i++) {
        // ตรวจสอบบิตที่ i
        if (num & (1u << i)) {
            // ตั้งบิตที่ตำแหน่งกลับด้าน
            reversed |= (1u << ((totalBits - 1) - i));
        }
    }
    return reversed;
}

int main() {
    unsigned int n = 21;
    cout << "The number is: " << n << endl;
    cout << "Reversed bits: " << reverseBitNumber(n);
    return 0;
}

ผลลัพธ์

The number is: 21
Reversed bits: 2818572288

วิธีที่ 2: Bit Shifting (Efficient)

unsigned int reverseBitNumber(unsigned int n) {
    unsigned int remainingShifts = sizeof(n) * 8 - 1;
    unsigned int reversed = n;
    
    n >>= 1;  // ข้ามบิตแรกที่ already ใน reversed
    
    while (n) {
        reversed <<= 1;           // เลื่อน reversed ทำช่องว่าง
        reversed |= (n & 1);      // นำบิต LSB ของ n มาต่อ
        n >>= 1;                  // เลื่อน n ไปหาบิตถัดไป
        remainingShifts--;
    }
    
    // เติมศูนย์สำหรับบิตที่เหลือ
    reversed <<= remainingShifts;
    
    return reversed;
}

วิธีที่ 3: Lookup Table (Fastest for Repeated Calls)

// Precompute reversed bytes (0-255)
unsigned char reverseByte[256];

void initReverseByteTable() {
    for (int i = 0; i < 256; i++) {
        unsigned char b = i;
        unsigned char r = 0;
        for (int j = 0; j < 8; j++) {
            r = (r << 1) | (b & 1);
            b >>= 1;
        }
        reverseByte[i] = r;
    }
}

unsigned int reverseBitsFast(unsigned int n) {
    return (reverseByte[n & 0xFF] << 24) |
           (reverseByte[(n >> 8) & 0xFF] << 16) |
           (reverseByte[(n >> 16) & 0xFF] << 8) |
           (reverseByte[(n >> 24) & 0xFF]);
}

Complexity

สรุป

การกลับบิต (bit reversal) ใช้ใน FFT, cryptography, และ bit manipulation problems วิธี Lookup Table เร็วที่สุดสำหรับการใช้งานจริง แต่วิธี Bit Shifting ก็เพียงพอและเข้าใจง่ายกว่าสำหรับการแข่งขันเขียนโปรแกรม