/*
 * If difference between count of odd set bits (Bits set at odd positions)
 * and even set bits is multiple of 3 then is the number is multiple of 3.
 * Reference: http://www.geeksforgeeks.org/archives/511
 */
#include <iostream>
#include <stdlib.h>
#include <math.h>


using namespace std;

// function to check if n is a multiple of 3.

int isMultipleOf3(int n)
{
  int odd_count = 0;
  int even_count = 0;
  if(n < 0) n = -n;
  if(n==0) return 1;
  if(n==1) return 0;
  while(n)
  {
    // if odd bit is set then increment odd count
    if(n&1)
      odd_count++;
    n = n >> 1;
    // if even bit is set then increment even count
    if(n & 1)
      even_count++;
    n = n >> 1;
  }
  return isMultipleOf3(abs(odd_count - even_count));
}

int main()
{
  int num = 22;
  if (isMultipleOf3(num))
    cout << num << " is multiple of 3" << endl;
  else
    cout << num << " is not a multiple of 3" << endl;
  return 0;
}