หาตัวเลขมากที่สุดที่มี n บิต 1 และ m บิต 0 ใน C++

ในปัญหานี้ เราได้รับ n (จำนวน set bits) และ m (จำนวน unset bits) งานคือหาตัวเลขมากที่สุดที่มี binary representation ตรงตามเงื่อนไข

ตัวอย่าง

Input: n = 3, m = 1 Output: 14

Binary: 1110 (3 ones, 1 zero) = 14

วิธีการแก้ปัญหา: Bit Manipulation

1. สร้างตัวเลขที่มี (n+m) บิตเป็น 1 ทั้งหมด: (1 << (n+m)) - 1
2. Toggle off m บิตสุดท้าย (LSB): XOR กับ ((1 << m) - 1)

สูตร: ((1 << (n+m)) - 1) ^ ((1 << m) - 1)

ตัวอย่างโค้ด

#include <iostream>
using namespace std;

int findLargestNumber(int n, int m) {
    int maxNum = (1 << (n + m)) - 1;
    if (m == 0) return maxNum;
    int mask = (1 << m) - 1;
    return maxNum ^ mask;
}

int main() {
    int n = 5, m = 2;
    cout << "Largest number: " << findLargestNumber(n, m);
    return 0;
}

ผลลัพธ์

Largest number with 5 set bits and 2 unset bits is 124

124 = 1111100 (5 ones, 2 zeros)