이 문제에서 정수 X가 주어집니다. 우리의 임무는 0에서 X로 변환하는 데 수행되는 총 단계 수를 찾는 것입니다.
유효한 변환 − A에서 B로 한 번의 변환이 발생할 때 한 단계가 계산됩니다. 변환이 수행되는 조건은 A !=B 및 A &B =A(&는 비트 AND)입니다. 따라서 1단계는 A에서 B로 변환하는 것이며 0을 X로 변환하는 최대 단계 수를 계산하는 프로그램을 만들어야 합니다.
문제를 이해하기 위해 예를 들어 보겠습니다.
입력 - X =7
출력 - 3
설명 -
0에서 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.
이 문제를 해결하기 위해 0에서 X로의 최대 변환을 제공하는 X의 세트 비트 수를 계산할 것입니다.
최대 변환이 필요하므로 각 설정된 비트(값이 1인 비트)에 대해 단계적으로 이동해야 합니다. 비트 후 비트 변환은 0에서 X로 변환하는 최대 단계를 제공합니다.
A에서 B로의 변환에서 A의 모든 설정 비트는 B에 설정되어야 하지만 그 반대는 필요하지 않습니다. 따라서 최소 변환을 직접 만드는 0에 설정된 비트가 없기 때문에 최소 변환은 1이 될 수 있습니다.
우리가 취한 예에서 볼 수 있듯이 숫자와 비트 AND에 대한 이진 변환입니다.
예시
우리 솔루션의 구현을 보여주는 프로그램 −
//C++에서 비트 AND를 사용하여 0을 X로 변환하는 최대 단계를 찾는 프로그램
#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;
} 출력
The maximum number of steps to transform 0 to 7 with bitwise AND are 3