Tìm bù 1 của một số nguyên trong C++

Trong phần này, chúng ta sẽ xem cách tìm bù 1 (one's complement) của một số nguyên. Có thể dùng toán tử bù (~) để làm nhanh, nhưng nó sẽ tạo giá trị bù 32-bit (số nguyên 4 byte). Ở đây chúng ta muốn bù của số n-bit.

Ví dụ: số 22 có nhị phân là 10110. Giá trị bù là 01001 tức là 9. Làm sao tìm giá trị này? Trước tiên tìm số bit của số cho trước. Giả sử đếm được c (c = 5 cho 22). Ta tạo ra c số 1: 11111. Cách làm: dịch 1 sang trái c lần, sau đó trừ 1. Dịch 1 trái 5 lần được 100000, trừ 1 được 11111. Cuối cùng thực hiện XOR giữa 11111 và 10110 để ra bù.

Ví dụ mã C++

#include <iostream>
#include <cmath>
using namespace std;

int timBuMot(int n) {
    int soBit = floor(log2(n)) + 1;
    int tatCaMot = ((1 << soBit) - 1);
    return tatCaMot ^ n;
}

int main() {
    int so = 22;
    cout << "Bù 1 của " << so << " là: " << timBuMot(so);
}

Kết quả đầu ra

Bù 1 của 22 là: 9