เพิ่มค่าตัวเลขโดยจัดเรียงบิตใหม่ใน C++

โจทย์

ได้รับ Unsigned Number หาตัวเลขสูงสุดที่สามารถสร้างได้โดยใช้บิตของตัวเลขที่กำหนด

ถ้าตัวเลขอินพุตคือ 8 Binary Representation คือ

00000000000000000000000000001000

เพื่อให้สูงสุด ตั้ง MSB เป็น 1 ตัวเลขกลายเป็น 2147483648 Binary คือ

10000000000000000000000000000000

อัลกอริทึม

1. นับจำนวน Set Bits ใน Binary Representation
2. หาตัวเลขที่มี n Least Significant Bits เป็น 1
3. Shift ซ้าย (32 - n) ตำแหน่ง

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

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

unsigned getMaxNumber(unsigned num) {
    int n = __builtin_popcount(num);
    if (n == 32) {
        return num;
    }
    unsigned result = (1 << n) - 1;
    return (result << (32 - n));
}

int main() {
    unsigned n = 8;
    cout << "Maximum number = " << getMaxNumber(n) << endl;
    return 0;
}

ผลลัพธ์

Maximum number = 2147483648