Spread the love
- 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 multiple of 9 bool isMulOf9(int n) { // Base cases if (n == 0 || n == 9) return true; if (n < 9) return false; // if the number is greater than 9, then do this return isMulOf9((int)(n>>3) - (int)(n&7)); } int main() { if( isMulOf9(18) ) cout << "Given Number is multiple of 9 \n" << endl; else cout << "Given Number is not multiple of 9 \n" << endl; return 0; }
Code Explanation
- Here we pass number 18 as a function argument, which is multiple of 9.
- When first time function call occur, it checks for first two condition which becomes false, then it goes to return statement which work like follow
/* Bit Maigc */ (int)(n>>3) = (18>>3) = (0001 0010/Binary representation of 18/ >> 3) = 0000 0010 (int)(n&7) = (18 & 7) = (0001 0010 & 0000 0111) = 0000 0010 (int)(n>>3) - (int)(n&7) = 0
- Now return statement’s return value is zero(‘0’),
- And second time recursive call occur which returns true, means number is multiple of 9.
Suggested Reading
- Write a Macro’s Set,clear and toggle n’th bit using bit wise operators?
- Write a c program to implement XOR functionality with out using XOR(^) operator
- How to turn off a particular bit in a number?