Viết chương trình hiệu quả đảo bit của số C++

Trong bài toán này, cho một số nguyên không dấu n. Nhiệm vụ là tạo chương trình trả về số được tạo bằng cách đảo tất cả các bit của số.

Ví dụ:

Input

n = 1

Output

2147483648

Giải thích

nhị phân của 1: 000...0001, đảo ngược: 100...0000

Cách 1: Duyệt qua các bit của số. Tìm vị trí bit set là i. Kết quả đặt bit tại vị trí (tổng_số_bit - 1) - i.

Ví dụ minh họa

#include <iostream>
using namespace std;

unsigned int reverseBitNumber(unsigned int num) {
    unsigned int totalNumberOfBits = sizeof(num) * 8;
    unsigned int reverseNumber = 0;
    
    for (int i = 0; i < totalNumberOfBits; i++) {
        if (num & (1 << i))
            reverseNumber |= (1 << ((totalNumberOfBits - 1) - i));
    }
    return reverseNumber;
}

int main() {
    unsigned int n = 21;
    cout << "Số ban đầu: " << n << endl;
    cout << "Số đảo bit: " << reverseBitNumber(n);
    return 0;
}

Kết quả

Số ban đầu: 21
Số đảo bit: 2818572288

Cách 2: Dùng dịch bit

Dịch bit của số cho đến khi thành 0, đồng thời dịch vào số đảo, sau đó dịch tiếp các bit còn lại.

Ví dụ minh họa

#include <iostream>
using namespace std;

unsigned int reverseBitNumber(unsigned int n) {
    unsigned int rem_shift = sizeof(n) * 8 - 1;
    unsigned int reverseNumber = n;
    n >>= 1;
    
    while (n) {
        reverseNumber <<= 1;
        reverseNumber |= n & 1;
        n >>= 1;
        rem_shift--;
    }
    
    reverseNumber <<= rem_shift;
    return reverseNumber;
}

int main() {
    unsigned int n = 21;
    cout << "Số ban đầu: " << n << endl;
    cout << "Số đảo bit: " << reverseBitNumber(n);
    return 0;
}

Kết quả

Số ban đầu: 21
Số đảo bit: 2818572288