ในปัญหานี้เราได้รับตัวเลข N ซึ่งมีเพียงหนึ่งชุดบิตในการแทนค่าไบนารี งานของเราคือการหาตำแหน่งของบิตที่ตั้งไว้เท่านั้น หากตัวเลขมีชุดบิตเพียงชุดเดียวให้ส่งคืนตำแหน่งของตัวเลขมิฉะนั้นจะพิมพ์ตัวเลขที่ไม่ถูกต้อง
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
N = 32
ผลลัพธ์
6
คำอธิบาย
Binary representation of the number is 10000.
แนวทางการแก้ปัญหา
ข้อเท็จจริงประการหนึ่งที่ควรทราบก่อนดำเนินการต่อไปคือตัวเลขจะมีเพียง 1 ชุดบิตหากเป็นยกกำลัง 2 มิฉะนั้นจะมีจำนวนชุดบิตมากขึ้น
วิธีแก้ไขง่ายๆ คือเริ่มจากบิตขวาสุดแล้วตรวจสอบค่าของบิต เราจะใช้การวนซ้ำตรวจสอบว่ามีการตั้งค่าหรือไม่
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#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;
} ผลลัพธ์
The position of the number 64 is 7
อีกวิธีหนึ่งในการแก้ปัญหาคือการใช้ shift เพื่อเลื่อนตัวเลขไปทางขวาจนกลายเป็น 0 ในตอนท้าย จำนวนกะที่ทำไปถึง 0 คือตำแหน่งของบิตที่ตั้งไว้
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#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;
} ผลลัพธ์
The position of the number 64 is 7
อีกวิธีหนึ่งในการแก้ปัญหาคือการใช้สูตรคณิตศาสตร์ เรารู้ดีว่า
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)
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#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;
} ผลลัพธ์
The position of the number 64 is 7
