ตัวเลขต่ำสุดที่ใช้ set bits ของตัวเลขที่กำหนดใน C++

ข้อกำหนดโจทย์

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

ตัวอย่าง

ถ้า input = 10 คำตอบจะเป็น 3

Binary representation ของ 10 คือ 1010 และตัวเลขต่ำสุดที่มี 2 set bits คือ 0011 คือ 3

อัลกอริทึม

1. นับจำนวน set bits
2. (Number of set bits) ^ 2 - 1 แทนตัวเลขที่ลดลงแล้ว

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

#include <bits/stdc++.h>
using namespace std;
int getSetBits(int n) {
  int cnt = 0;
  while (n) {
    ++cnt;
    n = n & (n - 1);
  }
  return cnt;
}
int getMinNumber(int n){
  int bits = getSetBits(n);
  return pow(2, bits) - 1;
}
int main() {
  int n = 10;
  cout << "Minimum number = " << getMinNumber(n) << endl;
  return 0;
}

เมื่อคุณคอมไพล์และรันโปรแกรมด้านบน จะได้ผลลัพธ์ดังนี้

ผลลัพธ์

Minimum number = 3