Viết một phương pháp hiệu quả để kiểm tra xem một số có phải là bội số của 3 trong C ++ hay không

Ở đây, chúng ta cần viết một chương trình dùng để kiểm tra xem số đã cho có phải là bội của 3 hay không.

Một giải pháp tổng quát là một giải pháp nhỏ, cộng tất cả các chữ số của số đó và nếu tổng là bội của ba thì số đó chia hết cho 3 còn lại thì không. Nhưng giải pháp này không phải là giải pháp hiệu quả nhất.

Một giải pháp hiệu quả sẽ là sử dụng số lượng bit trong biểu diễn nhị phân của số. Nếu sự khác biệt giữa số lượng các bit đặt ở vị trí lẻ và số lượng các bit đã đặt ở vị trí chẵn là bội số của 3 thì số đó là bội số của 3.

Chúng ta sẽ sử dụng một vòng lặp và dịch chuyển các bit của số và đếm số bit là vị trí chẵn và lẻ. Cuối cùng, chúng tôi sẽ trả lại séc nếu chênh lệch là bội số của ba.

Hãy lấy một ví dụ để hiểu cách triển khai,

Đầu vào

n = 24

Đầu ra

even

Giải thích

binary representation = 11000
Evensetbits = 1 , oddsetbits = 1.
Difference = 0, it is divisible.

Chương trình cho thấy việc triển khai giải pháp của chúng tôi,

Ví dụ

#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(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;
}

Đầu ra

The number 1241 is not a multiple of 3