Viết phương pháp hiệu quả kiểm tra bội số của 3 C++

Cần viết chương trình kiểm tra số cho trước có phải bội số của 3 hay không.

Cách thông thường: cộng các chữ số, nếu tổng chia hết cho 3 thì số đó chia hết cho 3. Nhưng không hiệu quả nhất.

Cách hiệu quả: dùng số bit set trong biểu diễn nhị phân. Nếu hiệu giữa số bit set ở vị trí lẻ và số bit set ở vị trí chẵn là bội của 3 thì số đó chia hết cho 3.

Duyệt qua các bit, dịch bit và đếm bit set ở vị trí chẵn/lẻ. Cuối cùng kiểm tra hiệu có chia hết cho 3.

Ví dụ

Input – n = 24

Output – chia hết

Giải thích – nhị phân = 11000, bit chẵn set = 1, bit lẻ set = 1, hiệu = 0, chia hết.

Ví dụ minh họa

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

int isDivisibleBy3(int n) {
    int oddBitCount = 0;
    int evenBitCount = 0;
    
    if (n < 0) n = -n;
    if (n == 0) return 1;
    if (n == 1) return 0;
    
    while (n) {
        if (n & 1) oddBitCount++;
        if (n & 2) evenBitCount++;
        n = n >> 2;
    }
    
    return isDivisibleBy3(abs(oddBitCount - evenBitCount));
}

int main() {
    int n = 1241;
    cout << "Số " << n;
    if (isDivisibleBy3(n))
        cout << " là bội số của 3";
    else
        cout << " không phải bội số của 3";
    return 0;
}

Kết quả

Số 1241 không phải bội số của 3