Số bước tối đa để biến đổi 0 thành X bằng phép AND bitwise trong C++

Trong bài toán này, ta được cho một số nguyên X. Nhiệm vụ là tìm tổng số bước để biến đổi từ 0 thành X.

Biến đổi hợp lệ – Một bước được đếm khi biến đổi từ A sang B. Điều kiện: A != B và A & B = A (phép AND bitwise). Vậy 1 bước là biến đổi A → B, ta cần đếm số bước tối đa từ 0 đến X.

Ví dụ:

Đầu vào – X = 7

Đầu ra – 3

Giải thích –

Biến đổi từ 0 đến 7:

Bước 1: 0(00) → 1(01), 0 != 1 và 0&1 = 0, biến đổi 00⇒01
Bước 2: 1(001) → 3(011), 1 != 3 và 1&3 = 1, biến đổi 001⇒011
Bước 3: 3(0011) → 7(0111), 3 != 7 và 3&7 = 3, biến đổi 0011⇒0111.

Để giải quyết, ta đếm số bit 1 (set bits) trong X, chính là số bước biến đổi tối đa từ 0 đến X.

Vì cần số bước tối đa, ta tiến từng bit 1. Mỗi bit một bước sẽ cho số bước lớn nhất. Trong biến đổi A → B, tất cả bit 1 của A phải là bit 1 của B, nhưng ngược lại không cần. Do đó, số bước tối thiểu có thể là 1 vì 0 không có bit 1 nào.

Mã nguồn C++

Chương trình minh họa giải pháp –

// Chương trình tìm số bước tối đa biến đổi 0 thành X bằng bitwise AND trong C++

#include <bits/stdc++.h>
using namespace std;

int maxtransformation(int x) {
    int steps = 0;
    // Đếm số bit 1
    while (x) {
        steps += x & 1;
        x >>= 1;
    }
    return steps;
}

int main() {
    int x = 7;
    cout << "The maximum number of steps to transform 0 to " << x << " with bitwise AND are " << maxtransformation(x);
    return 0;
}

Kết quả

The maximum number of steps to transform 0 to 7 with bitwise AND are 3