หาตำแหน่งของบิตเซตเพียงตัวเดียวใน C++

ในปัญหานี้ เราได้รับตัวเลข N ซึ่งมีบิตเซต (set bit) เพียงตัวเดียวในการแทนค่าไบนารี งานของเราคือหาตำแหน่งของบิตเซตเพียงตัวเดียว ถ้าตัวเลขมีบิตเซตเพียงตัวเดียว ให้คืนค่าตำแหน่ง มิฉะนั้นพิมพ์ว่า invalid number

มาดูตัวอย่างเพื่อเข้าใจปัญหา

Input

N = 32

Output

6

อธิบาย

การแทนค่าไบนารีของตัวเลขคือ 100000

วิธีแก้ปัญหา

ข้อเท็จจริงที่ต้องรู้ก่อนคือ ตัวเลขจะมีบิตเซตเพียง 1 ตัวก็ต่อเมื่อมันเป็นกำลังของ 2 มิฉะนั้นจะมีบิตเซตมากกว่า 1 ตัว

วิธีแก้ที่ง่ายคือเริ่มจากบิตขวามือสุด และตรวจสอบค่าของบิต เราจะใช้ลูปเพื่อตรวจสอบว่ามันเป็นเซตหรือไม่

โปรแกรมแสดงการทำงานของวิธีแก้ (Bit Shifting)

ตัวอย่าง

#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 operation เลขขวาจนกว่าตัวเลขจะกลายเป็น 0 ณ ตอนสุดท้าย จำนวนครั้งที่ shift เพื่อให้ได้ 0 คือตำแหน่งของบิตเซต

โปรแกรมแสดงการทำงานของวิธีแก้ (Right Shift)

ตัวอย่าง

#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

อีกวิธีหนึ่งคือใช้สูตรคณิตศาสตร์ เรารู้ว่า

2^i = n โดยที่ n คือตัวเลข และ i คือตำแหน่งของตัวเลข 
ค่าของ i สามารถหาได้จากสูตร i = log2(n)

โปรแกรมแสดงการทำงานของวิธีแก้ (Logarithm)

ตัวอย่าง

#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