Check if a number is multiple of 9 using bitwise operators

Given a number n, write a function that returns true if n is divisible by 9, else false. The most simple way to check for n’s divisibility by 9 is to do n%9.
Another method is to sum the digits of n. If sum of digits is multiple of 9, then n is multiple of 9.
The above methods are not bitwise operators based methods and require use of % and /.
The bitwise operators are generally faster than modulo and division operators. Following is a bitwise operator based method to check divisibility by 9.

C++

 // C++ program to check if a number // is multiple of 9 using bitwise operators #include using namespace std;    // Bitwise operator based function to check divisibility by 9 bool isDivBy9(int n) {     // Base cases     if (n == 0 || n == 9)         return true;     if (n < 9)         return false;        // If n is greater than 9, then recur for [floor(n/9) - n%8]     return isDivBy9((int)(n >> 3) - (int)(n & 7)); }    // Driver program to test above function int main() {     // Let us print all multiples of 9 from 0 to 100     // using above method     for (int i = 0; i < 100; i++)         if (isDivBy9(i))             cout << i << " ";     return 0; }

Java

 // Java program to check if a number // is multiple of 9 using bitwise operators import java.lang.*;    class GFG {        // Bitwise operator based function     // to check divisibility by 9     static boolean isDivBy9(int n)     {            // Base cases         if (n == 0 || n == 9)             return true;         if (n < 9)             return false;            // If n is greater than 9, then         // recur for [floor(n/9) - n%8]         return isDivBy9((int)(n >> 3) - (int)(n & 7));     }        // Driver code     public static void main(String arg[])     {            // Let us print all multiples of 9 from         // 0 to 100 using above method         for (int i = 0; i < 100; i++)             if (isDivBy9(i))                 System.out.print(i + " ");     } }    // This code is contributed by Anant Agarwal.

Python3

 # Bitwise operator based # function to check divisibility by 9    def isDivBy9(n):        # Base cases     if (n == 0 or n == 9):         return True     if (n < 9):         return False         # If n is greater than 9,     # then recur for [floor(n / 9) - n % 8]     return isDivBy9((int)(n>>3) - (int)(n&7))    # Driver code    # Let us print all multiples # of 9 from 0 to 100 # using above method for i in range(100):     if (isDivBy9(i)):         print(i, " ", end ="")    # This code is contributed # by Anant Agarwal.

C#

 // C# program to check if a number // is multiple of 9 using bitwise operators using System;    class GFG {        // Bitwise operator based function     // to check divisibility by 9     static bool isDivBy9(int n)     {         // Base cases         if (n == 0 || n == 9)             return true;         if (n < 9)             return false;            // If n is greater than 9, then         // recur for [floor(n/9) - n%8]         return isDivBy9((int)(n >> 3) - (int)(n & 7));     }        // Driver code     public static void Main()     {         // Let us print all multiples of 9 from         // 0 to 100 using above method         for (int i = 0; i < 100; i++)             if (isDivBy9(i))                 Console.Write(i + " ");     } }    // This code is contributed by nitin mittal.

PHP

 > 3) -                      (\$n & 7)); }        // Driver Code     // Let us print all multiples     // of 9 from 0 to 100     // using above method     for (\$i = 0; \$i < 100; \$i++)         if (isDivBy9(\$i))             echo \$i ," ";                // This code is contributed by nitin mittal ?>

/div>

Output:

0 9 18 27 36 45 54 63 72 81 90 99

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.