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

โจทย์

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

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

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

อินพุต

เอาต์พุต

อัลกอริธึม

กำหนดตัวเลข 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 + 1 == getSetBitsCount(i)) { 
            return i; 
        } 
        i += 1; 
    } 
} 

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

ผลลัพธ์

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