Check if a number is multiple of 9 using bitwise operators

general
1

Hi all.

In this article (link : 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?

1 Like
2

source: same page

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.

3

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.

2 Likes
4

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.

5

Thanx a lot.