Tìm vị trí bit được đặt duy nhất trong C++

Trong bài toán này, cho số N có duy nhất 1 bit được đặt (set bit) trong biểu diễn nhị phân. Nhiệm vụ là tìm vị trí bit đó. Nếu số có 1 bit set trả về vị trí, ngược lại in "invalid number".

Ví dụ minh họa:

Đầu vào

N = 32

Đầu ra

6

Giải thích

Biểu diễn nhị phân của 32 là 100000.

Phương pháp giải

Số chỉ có 1 bit set nếu là lũy thừa của 2. Cách 1: Kiểm tra từ bit phải nhất, dùng vòng lặp kiểm tra bit set.

Chương trình (Cách 1):

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; 
}

Kết quả

The position of the number 64 is 7

Cách 2: Dịch phải (>>) cho đến khi số = 0. Số lần dịch = vị trí bit set.

Chương trình (Cách 2):

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; 
}

Kết quả

The position of the number 64 is 7

Cách 3: Dùng công thức toán học. 2^i = n => i = log₂(n). Vị trí = log₂(n) + 1.

Chương trình (Cách 3):

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; 
}

Kết quả

The position of the number 64 is 7