หาจำนวนคำตอบของสมการ n = x + n XOR x ด้วย C++

ในบทความนี้ เราจะหาจำนวนคำตอบของสมการ n = x + n ⊕ x กล่าวคือ เราต้องหาจำนวนค่า x ที่เป็นไปได้ด้วยค่า n ที่กำหนด โดยที่ n = x + n ⊕ x โดยที่ ⊕ แทนการดำเนินการ XOR

ตอนนี้เราจะอภิปรายข้อมูลครบถ้วนเกี่ยวกับจำนวนคำตอบของ n = x + n ⊕ x พร้อมตัวอย่างที่เหมาะสม

วิธี Brute Force

เราสามารถใช้วิธี Brute Force เพื่อหาจำนวนคำตอบ กล่าวคือ สำหรับค่า n ที่กำหนด เราลองค่า x ทุกจำนวนเต็มตั้งแต่ 0 และตรวจสอบว่าสมการเป็นจริงหรือไม่ ค่า x ควรน้อยกว่าหรือเท่ากับ n เพราะการบวกค่าที่มากกว่า n กับ (n ⊕ x) จะไม่มีทางคืนค่า n เป็นคำตอบ

ตัวอย่าง

หาค่า x หนึ่งค่าสำหรับ n = 3?

n = x + n ⊕ x ใส่ x = 0, 3 = 0 + 3 ⊕ 0, 3 ⊕ 0 = 3, 3 = 3 LHS = RHS (x = 0 ตอบโจทย์) ดังนั้น x = 0 เป็นคำตอบหนึ่ง

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

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

int main() {
    int n = 3, c = 0;
    for (int x = 0; x <= n; ++x) // ลูปให้ค่า x จาก 0 ถึง n
        if (n == x + n ^ x) // ตรวจสอบว่าค่า x ตอบโจทย์สมการหรือไม่
            ++c;
    cout << "Number of possible solutions : " << c;
    return 0;
}

ผลลัพธ์

Number of possible solutions : 4

นี่คือโปรแกรม C++ เรียบง่ายสำหรับหาจำนวนคำตอบของ n = x + n ⊕ x โดยใช้วิธี Brute Force

วิธีที่มีประสิทธิภาพ (Efficient Approach)

ในวิธีนี้ หากเราดู n ในรูปแบบไบนารี เราต้องหาจำนวนบิตที่ตั้งค่าเป็น 1 และจากสมการ เราสามารถสรุปได้ว่า หาก n มีบิตตั้งค่า 1 แล้ว x จะต้องมีบิตตั้งค่า 1 หรือ n ⊕ x จะต้องมีบิตตั้งค่า 1 เพราะ 1 ⊕ 1 = 0 หมายความว่า n ⊕ x ไม่มีบิตนั้น ตอนนี้เราสามารถสรุปจำนวนการเรียงสำหรับบิตที่ตั้งค่าใน n ได้ คือ 2^(จำนวนบิตที่ตั้งค่า)

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

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

int main() {
    int n = 3, no_of_setbits = 0;
    // เริ่มต้น n ด้วยค่า และนับบิตที่ตั้งค่าเป็น 0
    while (n != 0) {
        no_of_setbits = no_of_setbits + (n % 2);
        // ตรวจสอบว่าตัวเลขมีบิตตั้งค่าหรือไม่
        n = n / 2;
    }
    int result = 1 << no_of_setbits;
    // คำนวณจำนวนคำตอบที่เป็นไปได้ด้วย 2^setbits
    cout << " Number of possible solutions : " << result;
    return 0;
}

ผลลัพธ์

Number of possible solutions : 4

ความซับซ้อนของโปรแกรม

ความซับซ้อนด้านเวลาของวิธีนี้คือ O(log n) เนื่องจากเรานับบิตที่ตั้งค่าใน n ซึ่งดีกว่าวิธี Brute Force ที่เป็น O(n) มาก

สรุป

ในบทความนี้ เราแก้ปัญหาการหาจำนวนคำตอบของสมการ n = x + n ⊕ x เรายังเรียนรู้โปรแกรม C++ สำหรับปัญหานี้ และวิธีการแก้ปัญหาทั้งหมด สามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, Java, Python ได้เช่นกัน หวังว่าบทความนี้จะเป็นประโยชน์