วิธีตรวจสอบว่าตัวเลขเป็นพหุคูณของ 3 อย่างมีประสิทธิภาพใน C++

โจทย์

เขียนโปรแกรมตรวจสอบว่าตัวเลขที่กำหนดเป็นพหุคูณของ 3 (หาร 3 ลงตัว) หรือไม่

วิธีทั่วไป (Naive)

รวมหลักของตัวเลขทั้งหมด หากผลรวมหาร 3 ลงตัว ตัวเลขก็หาร 3 ลงตัว

Time: O(log₁₀ n) - ต้องดึงทุกหลัก

วิธีที่มีประสิทธิภาพ (Efficient) - ใช้ Bit Counting

ทฤษฎี: ใน binary representation หาก ความต่างระหว่างจำนวนบิต 1 ที่ตำแหน่งคี่ และตำแหน่งคู่ เป็นพหุคูณของ 3 ตัวเลขก็จะเป็นพหุคูณของ 3

ตัวอย่าง: n = 24 (binary: 11000)
ตำแหน่งคี่ (1, 3, 5...): บิต 1 อยู่ที่ตำแหน่ง 3 และ 4? รอ 24 = 11000₂ = 16+8
bit 4 (16's place): 1 (even position - 0-indexed: 4)
bit 3 (8's place): 1 (odd position: 3)
Even bits: 1, Odd bits: 1, Diff = 0 → หาร 3 ลงตัว ✓

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

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

bool isDivisibleBy3(int n) {
    int oddBitCount = 0;
    int evenBitCount = 0;
    
    if (n < 0) n = -n;  // handle negative
    if (n == 0) return true;
    if (n == 1) return false;
    
    while (n) {
        if (n & 1) oddBitCount++;     // bit 0 (LSB) = odd position
        if (n & 2) evenBitCount++;    // bit 1 = even position
        n >>= 2;  // shift 2 bits ทีละครั้ง
    }
    
    return isDivisibleBy3(abs(oddBitCount - evenBitCount));
}

int main() {
    int n = 1241;
    cout << "The number " << n;
    if (isDivisibleBy3(n)) cout << " is a multiple of 3";
    else cout << " is not a multiple of 3";
    return 0;
}

ผลลัพธ์

The number 1241 is not a multiple of 3

การทำงานของอัลกอริทึม

1. นับบิต 1 ที่ตำแหน่งคี่ (0, 2, 4, ...) → oddBitCount
2. นับบิต 1 ที่ตำแหน่งคู่ (1, 3, 5, ...) → evenBitCount
3. คำนวณความต่าง |odd - even|
4. Recursive เรียกฟังก์ชันซ้ำจนได้คำตอบ (base case: 0=true, 1=false)

Complexity

• Time: O(log₂ n) - จำนวนบิตของ n
• Space: O(log₂ n) - recursion depth (สามารถทำ iterative ได้)

Iterative Version (หลีกเลี่ยง Recursion)

bool isDivisibleBy3Iterative(int n) {
    if (n < 0) n = -n;
    while (n >= 3) {  // ลดขนาดจนเหลือ 0,1,2
        int odd = 0, even = 0;
        while (n) {
            if (n & 1) odd++;
            if (n & 2) even++;
            n >>= 2;
        }
        n = abs(odd - even);
    }
    return n == 0;
}

สรุป

วิธี Bit Counting นี้มีประสิทธิภาพทางทฤษฎี (O(log n) bit operations) แต่ในทางปฏิบัติบน CPU สูงสุด n % 3 == 0 เร็วกว่ามาก เพราะมี hardware division instruction วิธีนี้เหมาะสำหรับระบบที่ไม่มี division instruction หรือการศึกษาอัลกอริทึม