Tìm số lớn nhất nhỏ hơn X có tối đa K bit được đặt trong C++

Trong hướng dẫn này, chúng ta sẽ viết một chương trình tìm số lớn nhất nhỏ hơn số X cho trước và có tối đa K bit được đặt (set bit).

Các bước giải quyết

• Khởi tạo các số X và K.
• Tìm số bit được đặt trong số X.
• Viết một vòng lặp chạy (số bit được đặt của X - K) lần:
  • Cập nhật giá trị X bằng X & (X - 1).
• Trả về X.

Ví dụ

Dưới đây là mã nguồn C++:

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

int largestNumberWithKBits(int x, int k) { 
    int set_bit_count = __builtin_popcount(x); 
    if (set_bit_count <= k) { 
        return x; 
    } 
    int diff = set_bit_count - k; 
    for (int i = 0; i < diff; i++) { 
        x &= (x - 1); 
    } 
    return x; 
} 

int main() { 
    int x = 65, k = 2; 
    cout << largestNumberWithKBits(x, k) << endl; 
    return 0; 
}

Kết quả

Nếu bạn chạy mã trên, kết quả sẽ là:

65

Kết luận

Nếu bạn có bất kỳ thắc mắc nào về hướng dẫn này, hãy để lại bình luận bên dưới.