A number is multiple of 3

There is a pattern in binary representation of the number that can be used to find if number is a multiple of 3. 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.

Example : 23 (00..10111)

1. Get count of all set bits at odd positions (For 23 it’s 3).
2. Get count of all set bits at even positions (For 23 it’s 1).
3. If difference of above two counts is a multiple of 3 then number is also a >multiple of 3.

(For 23 it’s 2 so 23 is not a multiple of 3)
Take some more examples like 21, 15, etc…

Algorithm: isMutlipleOf3(n)

1. Make n positive if n is negative.
2. If number is 0 then return 1
3. If number is 1 then return 0
4. Initialize: odd_count = 0, even_count = 0
5. Loop while n != 0
   a) If rightmost bit is set then increment odd count.
   b) Right-shift n by 1 bit
   c) If rightmost bit is set then increment even count.
   d) Right-shift n by 1 bit
6. return isMutlipleOf3(odd_count - even_count)

//cpp program to check if n is a multiple of 3
#include <stdio.h>
#include <math.h>
//Function to check if n is a multiple of 3
int isMultipleOf3(int n)
{
    int odd_count = 0;
    int even_count = 0;
    
    /*Make no positive if +n is a multiple of 3
    then is -n. We are doing this to avoid stack
    overflow in recursion*/
    if(n < 0) n = -n;
    if(n == 0) return 1;
    if(n == 1) return 0;
    
    while(n)
    {
        if(n & 1)//If odd bit is set then increment odd counter
        odd_count++;
        n = n >> 1;
        
        if(n & 1)//If even bit is set then increment odd counter
        even_count++;
        n = n >> 1;
    }
    
    return isMultipleOf3(abs(odd_count - even_count));
}
//program to test function isMultipleOf3
int main()
{
    int n;
    scanf("%d",&n);
    
    if(isMultipleOf3(n))
        printf("%d is a isMultipleOf3 number!!!",n);
    else
    printf("%d is not a isMultipleOf3 number!!!",n);
    return 0;
}

You can leave me a message if you find out any mistake in my diary, I'll correct it, thanks.