ตัวเลขถัดไปที่มากกว่าและมีจำนวนบิตเซตเท่ากันใน C++

โจทย์

เราได้รับตัวเลข n เราต้องหาตัวเลขที่มากกว่า n และมีจำนวนบิตเซต (set bits) เท่ากับ n ในการแทนค่าทศนิยมสอง

หลัก 1 ในการแทนค่าทศนิยมสองเรียกว่า set bit

มาดูตัวอย่างกัน

อินพุต

124

เอาต์พุต

143

อัลกอริธึม

• กำหนดตัวเลข n
• เขียนฟังก์ชันหาจำนวนบิตเซต
• กำหนดตัวแปรวนรอบด้วย n + 1
• เขียนลูปไม่รู้จบ
  • ตรวจสอบจำนวนบิตเซตของตัวเลขเท่ากับจำนวนบิตเซตของ n
  • คืนค่าตัวเลขเมื่อเจอ
  • เพิ่มตัวเลข

การนำไปใช้งาน

ต่อไปนี้เป็นการนำไปใช้งานของอัลกอริธึมข้างต้นใน C++

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

int getSetBitsCount(int n) { 
    int count = 0; 
    while (n) { 
        if (n % 2 == 1) { 
            count += 1; 
        } 
        n /= 2; 
    } 
    return count; 
} 

int getNextGreaterElementWithSameSetBits(int n) { 
    int setBitsCount = getSetBitsCount(n); 
    int i = n + 1; 
    while (true) { 
        if (setBitsCount == getSetBitsCount(i)) { 
            return i; 
        } 
        i += 1; 
    } 
} 

int main() { 
    int n = 124; 
    cout << getNextGreaterElementWithSameSetBits(n) << endl; 
    return 0; 
}

ผลลัพธ์

หากคุณรันโค้ดข้างต้น คุณจะได้ผลลัพธ์ดังนี้

143