คัดลอก Set Bits ในช่วงที่กำหนด (Copy Set Bits in Range) ใน C++

โจทย์ปัญหา

ได้รับจำนวนเต็มสองจำนวน x และ y และช่วงบิต [l, r] (1-indexed) ให้ คัดลอกบิตที่เป็น 1 จาก y ไป x เฉพาะในช่วงที่กำหนด คืนค่า x ที่แก้ไขแล้ว

ตัวอย่าง

Input: x = 10 (1010), y = 13 (1101), l = 2, r = 3
Binary:

x = 1010
y = 1101
Range [2,3]: bits 2-3 of y = 10 (binary)
Copy to x: 1010 | 0100 = 1110 (14)

Output: 14

แนวคิดการแก้ปัญหา

1. วนลูปบิต i จาก l ถึง r
2. สร้าง Mask: mask = 1 << (i-1) (1-indexed → 0-indexed)
3. ถ้า y & mask เป็น 1 → Set bit ใน x: x |= mask

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

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

void copySetBits(unsigned& x, unsigned y, unsigned l, unsigned r) {
    // Validate range (1-32 for 32-bit unsigned)
    if (l < 1 || r > 32) return;

    for (int i = l; i <= r; i++) {
        unsigned mask = 1u << (i - 1);  // 1-indexed to 0-indexed
        if (y & mask) {
            x |= mask;  // Set bit in x
        }
    }
}

int main() {
    unsigned x = 10, y = 13, l = 2, r = 3;
    copySetBits(x, y, l, r);
    cout << "Modified x: " << x << endl;  // 14
    return 0;
}

ผลลัพธ์

Modified x: 14

Optimized Version (O(1) - No Loop)

void copySetBitsFast(unsigned& x, unsigned y, unsigned l, unsigned r) {
    if (l < 1 || r > 32) return;

    // Create mask for range [l, r]
    unsigned mask = ((1u << (r - l + 1)) - 1) << (l - 1);
    // Extract bits from y in range, apply to x
    x |= (y & mask);
}

คำอธิบาย Optimized Version

1. (1u << (r - l + 1)) - 1 → สร้างบิต 1 ติดกัน (r-l+1) ตัว: เช่น r=3,l=2 → 3 bits → 111
2. << (l-1) → เลื่อนไปตำแหน่งที่ถูกต้อง: 111 << 1 = 1110 (bits 2,3,4)
3. y & mask → ดึงเฉพาะบิตในช่วงจาก y
4. x |= ... → Set บิตเหล่านั้นใน x

Complexity Analysis

คำอธิบายเพิ่มเติม

• ใช้ unsigned เพื่อหลีกเลี่ยง Undefined Behavior กับ Shift
• 1-indexed ตามโจทย์ (Bit 1 = LSB)
• ประยุกต์: Bit Manipulation, Flags, Permissions, Compression
• C++20: ใช้ std::bit_ceil, std::popcount ช่วยได้

ตัวอย่างการใช้งานจริง

// Copy permission bits from user to group (bits 6-8)
unsigned userPerm = 0755;  // rwxr-xr-x
unsigned groupPerm = 0;
copySetBitsFast(groupPerm, userPerm, 7, 9);  // Copy rwx (bits 7-9)

Convex Hull ด้วย Graham Scan Algorithm ใน C++

Else และ Switch Statements พร้อม Initializers ใน C++17