Fastest Way to check divisibility by 3

When the number is small directly check its divisibility by 3 by dividing it . works fine but if number is large this technique is no more best technique to check divisibility ..

Other way is by checking divisibility of sum of its digit . but this technique is also not effective because to find each digit we need to divide again & again by 10.

But there exist a much faster way to check this . 

Now think about binary representation of a number in binary . Since we generally  ignore property of number in binary that's why you did't find this till now .

Related Post :  Test your Programming Skill : P-1

Concept :

find out number of set odd position  bit from right  (let say it odd_set ) & find number of set even position bit from right (let say is even_set ). set bit means has value 1.

Now if difference of odd_set & even_set divisible by 3 than it is divisible otherwise not divisible by 3 .

& treat 0 & 1 as special case ..

Related Post : How to get ip address of user in PHP

C++ Code :

1. /*
2.   to check divisibility of a number by 3
3.   ..Most efficent way to check if number is large;
4. */
5. /*
6.   **************************************** CONCEPT **********************************
7.   it is based on concept that
8.   (total set bit at odd position from right - total set bit at even position )
9.   is divisible by 3 than Number is divisible by 3
10.   ************************************************************************************
11. */
12. #include<iostream>
13. #include<math.h>
14. using namespace std;
16. int IsDivBy3(int n)   //function def
17. {
18.         int even=0,odd=0;
19.        
20.         /****************special case****************/
21.         if(n==0) return 1;
22.         else if(n==1) return 0;
23.         /******************************************/
24.        
25.         if(n<0) n=-n; //to make number positive;
26.        
27.         while(n>0)
28.          {
29.                 if(n & 1)  //and operation
30.                    odd++;
31.                 n=n>>1; //right sift in binary by 1 ex: 1011 -> 011
32.                
33.                 if(n & 1) //and operation
34.                    even++;
35.                 n=n>>1;  //right sift in binary by 1 ex: 1011 -> 011
36.          }
37.          if((abs(even-odd))%3==0)
38.             return(1);
39.         else
40.             return(0);
41. }
43. main()
44. {
45.         int n;
46.         cout<<"enter number to check divisibility by 3 : ";
47.         cin>>n;
48.         if(IsDivBy3(n))   //call this function to check it return 1 if divisible otherwise 0
49.            cout<<"divisible";
50.         else
51.            cout<<"Not divisible";
52.            
53.         return 0;
54. }

Hope you enjoy this technique ..

Related Post : TOWER OF HANOI

YOu can develop your algorithm and make it public .. contact us query.b2cs@gmail.com
and you can post your content & algorithm on this blog ..