Đếm số 0 đuôi trong biểu diễn nhị phân của số dùng Bitset trong C++

Cho một số nguyên num làm đầu vào. Mục tiêu là tìm số lượng số 0 đuôi trong biểu diễn nhị phân của num sử dụng bitset.

bitset lưu trữ các bit 0 và 1 trong nó. Nó là một mảng các bit.

Ví dụ

Đầu vào

num = 10

Đầu ra

Số 0 đuôi trong biểu diễn nhị phân dùng Bitset là: 1

Giải thích

Số 10 trong nhị phân được biểu diễn là 1010 nên số 0 đuôi là 1.

Đầu vào

num = 64

Đầu ra

Số 0 đuôi trong biểu diễn nhị phân dùng Bitset là: 6

Giải thích

Số 64 trong nhị phân được biểu diễn là 1000000 nên số 0 đuôi là 6.

Phương pháp sử dụng

Trong phương pháp này, chúng ta đang sử dụng bitset. Chúng ta sẽ thiết lập bitset với num bằng toán tử |. Bây giờ duyệt bitset bằng vòng lặp for, ngay khi gặp bit 1 đầu tiên thì thoát vòng lặp, ngược lại tăng biến đếm cho các số 0 đuôi.

• Nhận số nguyên num làm đầu vào.
• Hàm trailing_zeroes(int num) nhận num và trả về số lượng số 0 đuôi trong biểu diễn nhị phân dùng bitset.
• Khởi tạo biến đếm ban đầu là 0.
• Tạo một bitset<64> arr.
• Thiết lập nó với num như arr |= num.
• Duyệt arr bằng vòng lặp for từ i=0 đến i<64. Nếu arr[i] là 0 thì tăng biến đếm, ngược lại thoát vòng lặp.
• Trả về biến đếm làm kết quả ở cuối vòng lặp.

Ví dụ mã

#include <bits/stdc++.h> 
using namespace std; 

int trailing_zeroes(int num) {
    int count = 0;
    bitset<64> arr;
    arr |= num;
    
    for (int i = 0; i < 64; i++) {
        if (arr[i] == 0) {
            count++;
        } else {
            break;
        }
    }
    
    return count;
}

int main() {
    int num = 6;
    cout << "Số 0 đuôi trong biểu diễn nhị phân dùng Bitset là: " << trailing_zeroes(num);
    return 0;
}

Đầu ra

Nếu chạy mã trên, sẽ tạo ra đầu ra sau:

Số 0 đuôi trong biểu diễn nhị phân dùng Bitset là: 1