C++で数値が3の倍数であるかどうかを確認するための効率的なメソッドを作成する

ここでは、与えられた数が3の倍数であるかどうかをチェックするために使用されるプログラムを作成する必要があります。

一般的な解決策は簡単な解決策であり、数値のすべての桁を加算し、合計が3の倍数である場合、数値は3で割り切れます。それ以外の場合は割り切れません。しかし、このソリューションは最も効率的なソリューションではありません。

効率的な解決策は、数値の2進表現でビット数を使用することです。 奇数位置のセットビット数と偶数位置のセットビット数の差が3の倍数である場合、その数は3の倍数です。

ループを使用して、数値のビットをシフトし、偶数と奇数の位置にあるビットの数をカウントします。最後に、差が3の倍数であるかどうかのチェックを返します。

実装を理解するために例を見てみましょう

入力

n = 24

出力

even

説明

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

ソリューションの実装を示すプログラム

例

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

出力

The number 1241 is not a multiple of 3