Trong bài toán này, chúng ta được cung cấp một số N chỉ có một bit đặt trong biểu diễn nhị phân của nó. Nhiệm vụ của chúng ta là tìm vị trí của bit đặt duy nhất. Nếu số chỉ có một bit được thiết lập, hãy trả về vị trí của số, nếu không, hãy in số không hợp lệ.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
N = 32
Đầu ra
6
Giải thích
Binary representation of the number is 10000.
Phương pháp tiếp cận giải pháp
Một sự thật cần biết trước khi chúng ta tiếp tục là số sẽ chỉ có 1 bit đặt nếu nó là lũy thừa của 2. Nếu không, nó sẽ có nhiều hơn số bit đặt.
Một giải pháp đơn giản là bắt đầu từ bit ngoài cùng bên phải và sau đó kiểm tra giá trị của các bit. Chúng tôi sẽ sử dụng một vòng lặp để kiểm tra xem nó đã được thiết lập hay chưa.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#include <iostream>
using namespace std;
bool isPowerOfTwo(unsigned n) {
if(n>0) {
while(n%2 == 0)
n/=2;
if(n == 1)
return true;
}
if(n == 0 || n != 1)
return false;
return false;
}
int findPostionOfSetBit(unsigned n) {
unsigned i = 1, position = 1;
while (!(i & n)) {
i = i << 1;
++position;
}
return position;
}
int main(void){
int n = 64;
if(!isPowerOfTwo(n))
cout<<"Invalid Number!";
else
cout<<"The position of the number "<<n<<" is "<<findPostionOfSetBit(n);
return 0;
} Đầu ra
The position of the number 64 is 7
Một phương pháp thay thế để giải quyết vấn đề là sử dụng phép toán shift để chuyển số sang phải cho đến khi nó trở thành 0. Cuối cùng, số lần dịch chuyển được thực hiện để đạt đến 0 là vị trí của bit đã đặt.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#include <iostream>
using namespace std;
bool isPowerOfTwo(unsigned n) {
if(n>0) {
while(n%2 == 0)
n/=2;
if(n == 1)
return true;
}
if(n == 0 || n != 1)
return false;
return false;
}
int findPostionOfSetBit(unsigned n) {
unsigned position = 0;
while (n) {
n = n >> 1;
++position;
}
return position;
}
int main(void){
int n = 64;
if(!isPowerOfTwo(n))
cout<<"Invalid Number!";
else
cout<<"The position of the number "<<n<<" is
"<<findPostionOfSetBit(n);
return 0;
} Đầu ra
The position of the number 64 is 7
Thêm một phương pháp để giải quyết vấn đề đó là sử dụng các công thức toán học. Chúng tôi biết rằng,
2i = n, where n is the number and i is the position of the number The values of i here can be found using the formula, i = log2(n)
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#include <iostream>
#include <math.h>
using namespace std;
bool isPowerOfTwo(unsigned n) {
if(n>0) {
while(n%2 == 0)
n/=2;
if(n == 1)
return true;
}
if(n == 0 || n != 1)
return false;
return false;
}
int findPostionOfSetBit(unsigned n) {
unsigned position = log2(n) + 1; ;
return position;
}
int main(void){
int n = 64;
if(!isPowerOfTwo(n))
cout<<"Invalid Number!";
else
cout<<"The position of the number "<<n<<" is "<<findPostionOfSetBit(n);
return 0;
} Đầu ra
The position of the number 64 is 7