A number is multiple of 3
2018-09-02 本文已影响50人
Tedisaname
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)
- Get count of all set bits at odd positions (For 23 it’s 3).
- Get count of all set bits at even positions (For 23 it’s 1).
- 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)
- Make n positive if n is negative.
- If number is 0 then return 1
- If number is 1 then return 0
- Initialize: odd_count = 0, even_count = 0
- 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- 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.