Số lần lật bit tối thiểu để tối đa hóa số với k bit 1 trong C++

Đề bài

Cho hai số n và k, tìm số lần lật bit tối thiểu để tối đa hóa số n sao cho số kết quả có đúng k bit 1. Điều kiện: k < số bit của n.

Ví dụ

• n = 9, k = 2
• Nhị phân 9 = 1001 (4 bit)
• Số 4-bit lớn nhất có 2 bit 1 là 1100 = 12
• Chuyển 1001 → 1100 cần lật 2 bit

Thuật toán

1. Đếm số bit của n: bitCount = log2(n) + 1
2. Tìm số lớn nhất có k bit 1: maxNum = 2^k - 1
3. Dịch maxNum để có cùng số bit với n: maxNum = maxNum << (bitCount - k)
4. Tính n XOR maxNum và đếm số bit 1 của kết quả

Ví dụ mã C++

#include <iostream>
#include <cmath>
using namespace std;

int demBit1(int n){
    int cnt = 0;
    while (n) {
        ++cnt;
        n = n & (n - 1);
    }
    return cnt;
}

int minFlipsRequired(int n, int k){
    int bitCount, maxNum, flipCount;
    bitCount = log2(n) + 1;
    maxNum = pow(2, k) - 1;
    maxNum = maxNum << (bitCount - k);
    flipCount = n ^ maxNum;
    return demBit1(flipCount);
}

int main(){
    cout << "Số lần lật bit tối thiểu: " << minFlipsRequired(9, 2) << "\n";
    return 0;
}

Kết quả đầu ra

Số lần lật bit tối thiểu: 2