# Check if a number is multiple of 9 using bitwise operators **URL:** \ **Category:** general\ **Tags:** bitwise-operation\ **Created:** [March 29, 2014, 10:03am UTC](https://discuss.codechef.com/t/check-if-a-number-is-multiple-of-9-using-bitwise-operators/4954 "2014-03-29T10:03:59Z")\ **Posts on this page:** 5\ **Page:** 1
**Author:** ![herman](https://discuss.codechef.com/user_avatar/discuss.codechef.com/herman/32/3653_2.png) [@herman](https://discuss.codechef.com/u/herman)\ **Post date:** [March 29, 2014, 10:03am UTC](https://discuss.codechef.com/t/check-if-a-number-is-multiple-of-9-using-bitwise-operators/4954/1 "2014-03-29T10:03:59Z")
Hi all. In this article (link : [Check if a number is multiple of 9 using bitwise operators - GeeksforGeeks](http://www.geeksforgeeks.org/divisibility-9-using-bitwise-operators/) ) it is written that (n%8) is equal to (int)(n&7) ( in the function bool isDivBy9(int n) ). Can someone explain how this is correct? ---
**Author:** ![garakchy](https://discuss.codechef.com/user_avatar/discuss.codechef.com/garakchy/32/359366_2.png) [@garakchy](https://discuss.codechef.com/u/garakchy)\ **Post date:** [March 29, 2014, 11:08am UTC](https://discuss.codechef.com/t/check-if-a-number-is-multiple-of-9-using-bitwise-operators/4954/2 "2014-03-29T11:08:17Z")
source: [same page](http://www.geeksforgeeks.org/divisibility-9-using-bitwise-operators/) How does this work? n/9 can be written in terms of n/8 using the following simple formula. n/9 = n/8 - n/72 Since we need to use bitwise operators, we get the value of floor(n/8) using n\>\>3 and get value of n%8 using n&7. We need to write above expression in terms of floor(n/8) and n%8. n/8 is equal to “floor(n/8) + (n%8)/8″. Let us write the above expression in terms of floor(n/8) and n%8 n/9 = floor(n/8) + (n%8)/8 - [floor(n/8) + (n%8)/8]/9 n/9 = floor(n/8) - [floor(n/8) - 9(n%8)/8 + (n%8)/8]/9 n/9 = floor(n/8) - [floor(n/8) - n%8]/9 From above equation, n is a multiple of 9 only if the expression floor(n/8) – [floor(n/8) - n%8]/9 is an integer. This expression can only be an integer if the sub-expression [floor(n/8) - n%8]/9 is an integer. The subexpression can only be an integer if [floor(n/8) - n%8] is a multiple of 9. So the problem reduces to a smaller value which can be written in terms of bitwise operators. ---
**Author:** ![bunty93](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@bunty93](https://discuss.codechef.com/u/bunty93)\ **Post date:** [March 29, 2014, 11:14am UTC](https://discuss.codechef.com/t/check-if-a-number-is-multiple-of-9-using-bitwise-operators/4954/3 "2014-03-29T11:14:15Z")
## How N%8 is N&7? Suppose we are having N%8.We can find it by subtracting 8 from N until N is less than 8.So,this indicates that when the value is greater than or equal to M it doesn’t matter we only need the remainder. So now we come to bit operation the first(from LSB) 3 bit position produces 7 when all the bits are set.Now AND op with the first(from LSB) 3 bits with 7(111) will give us the bits which are set. 14%8 1110 0111 0110 i.e. 6. ---
**Author:** ![herman](https://discuss.codechef.com/user_avatar/discuss.codechef.com/herman/32/3653_2.png) [@herman](https://discuss.codechef.com/u/herman)\ **Post date:** [March 29, 2014, 12:23pm UTC](https://discuss.codechef.com/t/check-if-a-number-is-multiple-of-9-using-bitwise-operators/4954/4 "2014-03-29T12:23:01Z")
Thanx.But i was asking about this part only : (n%8) is equal to (int)(n&7) ( in the function bool isDivBy9(int n) ).I want to know how this is correct. ---
**Author:** ![herman](https://discuss.codechef.com/user_avatar/discuss.codechef.com/herman/32/3653_2.png) [@herman](https://discuss.codechef.com/u/herman)\ **Post date:** [March 29, 2014, 12:33pm UTC](https://discuss.codechef.com/t/check-if-a-number-is-multiple-of-9-using-bitwise-operators/4954/5 "2014-03-29T12:33:43Z")
Thanx a lot.