Trong bài toán này, chúng ta được cung cấp một số nguyên X. Nhiệm vụ của chúng ta là tìm tổng số bước được thực hiện để chuyển đổi từ 0 sang X.
Chuyển đổi hợp lệ - Một bước được tính khi một phép biến đổi diễn ra từ A đến B. Điều kiện để phép biến đổi diễn ra là A! =B và A &B =A (&là bitwise AND). Vì vậy, 1 bước đang chuyển đổi từ A thành B và chúng ta phải tạo một chương trình sẽ đếm số bước tối đa để chuyển đổi từ 0 thành X.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào - X =7
Đầu ra - 3
Giải thích -
Chúng ta phải chuyển đổi từ 0 thành 7.
Steps taken will be Step1: 0(00) to 1(01) , 0!= 1 and 0&1 = 0, transform 00=>01 Step2: 1(001) to 3(011) , 1!= 3 and 1&3 = 1, transform 001=>011 Step3: 3(0011) to 7(0111) , 3!= 7 and 3&7 = 3, tranform 0011=>0111.
Để giải quyết vấn đề này, chúng tôi sẽ đếm số lượng bit đặt trong X sẽ cho phép biến đổi tối đa từ 0 thành X.
Vì chúng ta cần biến đổi tối đa, chúng ta phải thực hiện từng bước cho từng bit đã đặt (bit có giá trị 1). Quá trình chuyển đổi từ bit này sang bit khác sẽ cung cấp các bước tối đa để chuyển đổi từ 0 thành X.
Trong phép biến đổi từ A sang B, tất cả các bit đã đặt của A nên được đặt trong B, nhưng điều ngược lại là không cần thiết. Vì vậy, phép biến đổi tối thiểu có thể là 1 vì không có bit nào được đặt bằng 0 tạo nên chuyển đổi nhỏ nhất trực tiếp.
Như chúng ta có thể thấy trong ví dụ mà chúng tôi đã thực hiện, chuyển đổi nhị phân trên các số và các AND bit của chúng.
Ví dụ
Chương trình hiển thị việc triển khai giải pháp của chúng tôi -
// Chương trình tìm Các bước tối đa để chuyể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;
// counting number of bits
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;
} Đầu ra
The maximum number of steps to transform 0 to 7 with bitwise AND are 3