นับจำนวนที่มีตัวเลข 1 ติดกันทั้งหมดในรูปแบบไบนารีใน C++

ภาพรวมปัญหา

ให้จำนวนเต็มบวก N ต้องการนับจำนวนที่น้อยกว่าหรือเท่ากับ N ที่มีตัวเลข 1 ติดกันทั้งหมดในรูปแบบไบนารี เช่น 1 (1), 3 (11), 7 (111), 15 (1111) เป็นต้น

ข้อสังเกตสำคัญ

จำนวนเหล่านี้มีรูปแบบเป็น 2ⁱ - 1 โดย i เริ่มจาก 1

• i=1: 2¹-1 = 1 (1)
• i=2: 2²-1 = 3 (11)
• i=3: 2³-1 = 7 (111)
• i=4: 2⁴-1 = 15 (1111)

ตัวอย่าง

Input: N = 15

Output: 4

คำอธิบาย: จำนวนคือ 1, 3, 7, 15

Input: N = 50

Output: 5

คำอธิบาย: จำนวนคือ 1, 3, 7, 15, 31

แนวทางแก้ปัญหา

1. ฟังก์ชัน allOnes(int n) คืนค่าจำนวนที่ตรงเงื่อนไข
2. ตัวแปร count เริ่มต้นที่ 0
3. วนลูป i จาก 1 ถึง n
4. ถ้า 2ⁱ - 1 ≤ n ให้เพิ่ม count
5. คืนค่า count

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

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

int allOnes(int n) {
    int count = 0;
    for (int i = 1; ; i++) {
        long long val = (1LL << i) - 1; // 2^i - 1
        if (val > n) break;
        count++;
    }
    return count;
}

int main() {
    int N = 23;
    cout << "Number having all 1's in binary: " << allOnes(N);
    return 0;
}

ผลลัพธ์

Number having all 1's in binary: 4

การปรับปรุงประสิทธิภาพ

แทนที่จะใช้ pow(2,i) ให้ใช้ bit shift (1LL << i) ซึ่งเร็วกว่าและไม่มีปัญหาความแม่นยำของ floating point

ความซับซ้อน

• เวลา: O(log N) - ลูปทำงานประมาณ log₂(N) รอบ
• พื้นที่: O(1)