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.

#include<iostream> 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; }

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 ofn%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) andn%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.

Tail Recursion

What is tail recursion? 
A recursive function is tail recursive when recursive call is the last thing executed by the function.For example the following C++ function print() is tail recursive.

// An example of tail recursive function void print(int n) {     if (n < 0)  return;     cout << " " << n;       // The last executed statement is recursive call     print(n-1); }

Why do we care?
The tail recursive functions considered better than non tail recursive functions as tail-recursion can be optimized by compiler. The idea used by compilers to optimize tail-recursive functions is simple, since the recursive call is the last statement, there is nothing left to do in the current function, so saving the current function’s stack frame is of no use.

Can a non-tail recursive function be written as tail-recursive to optimize it?
Consider the following function to calculate factorial of n. It is a non-tail-recursive function. Although it looks like a tail recursive at first look. If we take a closer look, we can see that the value returned by fact(n-1) is used in fact(n), so the call to fact(n-1) is not the last thing done by fact(n)

#include<iostream> using namespace std;   // A NON-tail-recursive function.  The function is not tail // recursive because the value returned by fact(n-1) is used in // fact(n) and call to fact(n-1) is not the last thing done by fact(n) unsigned int fact(unsigned int n) {     if (n == 0) return 1;       return n*fact(n-1); }   // Driver program to test above function int main() {     cout << fact(5);     return 0; }

The above function can be written as a tail recursive function. The idea is to use one more argument and accumulate the factorial value in second argument. When n reaches 0, return the accumulated value.

#include<iostream> using namespace std;   // A tail recursive function to calculate factorial unsigned factTR(unsigned int n, unsigned int a) {     if (n == 0)  return a;       return factTR(n-1, n*a); }   // A wrapper over factTR unsigned int fact(unsigned int n) {    return factTR(n, 1); }   // Driver program to test above function int main() {     cout << fact(5);     return 0; }

References:
http://en.wikipedia.org/wiki/Tail_call
http://c2.com/cgi/wiki?TailRecursion