Posted on by Kalkicode
Code Mathematics

# Number divisible by 9 using bitwise

The given problem is about determining whether a given number is divisible by 9 using bitwise operations. The code implements a recursive function that checks the divisibility of a number by 9 by using bitwise operations to optimize the calculation.

## Problem Statement

We want to check if a given number is divisible by 9 using bitwise operations instead of traditional arithmetic operations.

## Explanation with Example

Let's consider the number 81 as an example. In the code, we call the function `divisibleBy9(81)`. The function starts by checking the base cases. If the number is 9 or 0, it returns true as they are divisible by 9. Otherwise, it checks if the number is less than 9, in which case it returns false since it's not divisible by 9.

Now comes the bitwise operation part. The code uses two bitwise operations: right shift (`>>`) and bitwise AND (`&`). Here's how it works:

1. `num >> 3`: Right shifting a number by 3 is equivalent to dividing it by 8 (2^3) because it shifts the bits to the right by three positions, effectively removing the three least significant bits.

2. `num & 7`: Performing a bitwise AND operation with 7 (binary 0111) extracts the three least significant bits of the number.

Now, the recursive call `divisibleBy9((num >> 3) - (num & 7))` checks if the new number obtained from the difference is divisible by 9 using the same process.

## Pseudocode

``````function divisibleBy9(num):
if num is 9 or 0:
return true
if num < 9:
return false
return divisibleBy9((num >> 3) - (num & 7))
``````

## Algorithm Explanation

1. The function takes a number `num` as input.
2. If `num` is 9 or 0, it returns true (base case).
3. If `num` is less than 9, it returns false (base case).
4. The function calculates the new number as `(num >> 3) - (num & 7)`.
• `(num >> 3)` shifts the bits of `num` three positions to the right (equivalent to dividing by 8).
• `(num & 7)` extracts the three least significant bits of `num`.
• The difference of the two gives a new number.
5. The function makes a recursive call with the new number as the input.
6. Steps 2 to 5 continue until a base case is reached.
7. The final result of whether the number is divisible by 9 is returned.

## Code Solution

• The first two if statements are base cases. If the number is 0 or 9, the function returns true because 0 and 9 are both divisible by 9.
• If the number is less than 9, it cannot be divisible by 9 and the function returns false.
• If the number is greater than or equal to 9, the function recursively calls itself with the argument (num >> 3) - ((num & 7)), which is equivalent to subtracting 9 times the last digit of the number from the number itself. This is because 1000 (or 2^3) is the smallest power of 10 that is divisible by 9, and (num >> 3) is equivalent to dividing the number by 1000, while (num & 7) gives the last three digits of the number in binary. Subtracting these two values effectively removes the last digit from the number and subtracts it from the rest of the number, which is equivalent to subtracting 9 times the last digit.
• The recursion continues until the number becomes either 0 or a single-digit number that is either 0 or 9. If the resulting number is 0 or 9, the function returns true because the original number is divisible by 9 if and only if the resulting number is divisible by 9. If the resulting number is anything else, the function returns false because the original number is not divisible by 9.

## Program Solution

``````/*
C program for
Number divisible by 9 using bitwise
*/
#include <stdio.h>
#include <stdbool.h>
bool divisibleBy9(int num)
{
if (num == 9 || num == 0)
{
// Base case when number is 0 or 9
return true;
}
if (num < 9)
{
return false;
}
// Check divisibility of 9 using recursion
return divisibleBy9((num >> 3) - ((num & 7)));
}
int main(int argc, char
const *argv[])
{
int num = 81;
if (divisibleBy9(num))
{
printf("\n Number %d divisible by 9", num);
}
else
{
printf("\n Number %d is not divisible by 9", num);
}
num = 56;
if (divisibleBy9(num))
{
printf("\n Number %d divisible by 9", num);
}
else
{
printf("\n Number %d is not divisible by 9", num);
}
return 0;
}``````

#### Output

`````` Number 81 divisible by 9
Number 56 is not divisible by 9``````
``````/*
Java program for
Number divisible by 9 using bitwise
*/
class Divisibility
{
public boolean divisibleBy9(int num)
{
if (num == 9 || num == 0)
{
// Base case when number is 0 or 9
return true;
}
if (num < 9)
{
return false;
}
// Check divisibility of 9 using recursion
return divisibleBy9((num >> 3) - ((num & 7)));
}
public static void main(String[] args)
{
Divisibility task = new Divisibility();
int num = 81;
{
System.out.print("\n Number " + num + " divisible by 9");
}
else
{
System.out.print("\n Number " + num + " is not divisible by 9");
}
num = 56;
{
System.out.print("\n Number " + num + " divisible by 9");
}
else
{
System.out.print("\n Number " + num + " is not divisible by 9");
}
}
}``````

#### Output

`````` Number 81 divisible by 9
Number 56 is not divisible by 9``````
``````// Include header file
#include <iostream>
using namespace std;
/*
C++ program for
Number divisible by 9 using bitwise
*/
class Divisibility
{
public: bool divisibleBy9(int num)
{
if (num == 9 || num == 0)
{
// Base case when number is 0 or 9
return true;
}
if (num < 9)
{
return false;
}
// Check divisibility of 9 using recursion
return this->divisibleBy9((num >> 3) - ((num &7)));
}
};
int main()
{
Divisibility *task = new Divisibility();
int num = 81;
{
cout << "\n Number " << num << " divisible by 9";
}
else
{
cout << "\n Number " << num << " is not divisible by 9";
}
num = 56;
{
cout << "\n Number " << num << " divisible by 9";
}
else
{
cout << "\n Number " << num << " is not divisible by 9";
}
return 0;
}``````

#### Output

`````` Number 81 divisible by 9
Number 56 is not divisible by 9``````
``````// Include namespace system
using System;
/*
Csharp program for
Number divisible by 9 using bitwise
*/
public class Divisibility
{
public Boolean divisibleBy9(int num)
{
if (num == 9 || num == 0)
{
// Base case when number is 0 or 9
return true;
}
if (num < 9)
{
return false;
}
// Check divisibility of 9 using recursion
return this.divisibleBy9((num >> 3) - ((num & 7)));
}
public static void Main(String[] args)
{
Divisibility task = new Divisibility();
int num = 81;
{
Console.Write("\n Number " + num + " divisible by 9");
}
else
{
Console.Write("\n Number " + num + " is not divisible by 9");
}
num = 56;
{
Console.Write("\n Number " + num + " divisible by 9");
}
else
{
Console.Write("\n Number " + num + " is not divisible by 9");
}
}
}``````

#### Output

`````` Number 81 divisible by 9
Number 56 is not divisible by 9``````
``````package main
import "fmt"
/*
Go program for
Number divisible by 9 using bitwise
*/

func divisibleBy9(num int) bool {
if num == 9 || num == 0 {
// Base case when number is 0 or 9
return true
}
if num < 9 {
return false
}
// Check divisibility of 9 using recursion
return  divisibleBy9((num >> 3) - ((num & 7)))
}
func main() {

var num int = 81
if divisibleBy9(num) {
fmt.Print("\n Number ", num, " divisible by 9")
} else {
fmt.Print("\n Number ", num, " is not divisible by 9")
}
num = 56
if divisibleBy9(num) {
fmt.Print("\n Number ", num, " divisible by 9")
} else {
fmt.Print("\n Number ", num, " is not divisible by 9")
}
}``````

#### Output

`````` Number 81 divisible by 9
Number 56 is not divisible by 9``````
``````<?php
/*
Php program for
Number divisible by 9 using bitwise
*/
class Divisibility
{
public	function divisibleBy9(\$num)
{
if (\$num == 9 || \$num == 0)
{
// Base case when number is 0 or 9
return true;
}
if (\$num < 9)
{
return false;
}
// Check divisibility of 9 using recursion
return \$this->divisibleBy9((\$num >> 3) - ((\$num & 7)));
}
}

function main()
{
\$task = new Divisibility();
\$num = 81;
{
echo("\n Number ".\$num.
" divisible by 9");
}
else
{
echo("\n Number ".\$num.
" is not divisible by 9");
}
\$num = 56;
{
echo("\n Number ".\$num.
" divisible by 9");
}
else
{
echo("\n Number ".\$num.
" is not divisible by 9");
}
}
main();``````

#### Output

`````` Number 81 divisible by 9
Number 56 is not divisible by 9``````
``````/*
Node JS program for
Number divisible by 9 using bitwise
*/
class Divisibility
{
divisibleBy9(num)
{
if (num == 9 || num == 0)
{
// Base case when number is 0 or 9
return true;
}
if (num < 9)
{
return false;
}
// Check divisibility of 9 using recursion
return this.divisibleBy9((num >> 3) - ((num & 7)));
}
}

function main()
{
var task = new Divisibility();
var num = 81;
{
process.stdout.write("\n Number " + num + " divisible by 9");
}
else
{
process.stdout.write("\n Number " + num + " is not divisible by 9");
}
num = 56;
{
process.stdout.write("\n Number " + num + " divisible by 9");
}
else
{
process.stdout.write("\n Number " + num + " is not divisible by 9");
}
}
main();``````

#### Output

`````` Number 81 divisible by 9
Number 56 is not divisible by 9``````
``````#    Python 3 program for
#    Number divisible by 9 using bitwise
class Divisibility :
def divisibleBy9(self, num) :
if (num == 9 or num == 0) :
#  Base case when number is 0 or 9
return True

if (num < 9) :
return False

#  Check divisibility of 9 using recursion
return self.divisibleBy9((num >> 3) - ((num & 7)))

def main() :
num = 81
print("\n Number", num ,"divisible by 9", end = "")
else :
print("\n Number", num ,"is not divisible by 9", end = "")

num = 56
print("\n Number ", num ," divisible by 9", end = "")
else :
print("\n Number ", num ," is not divisible by 9", end = "")

if __name__ == "__main__": main()``````

#### Output

`````` Number 81 divisible by 9
Number  56  is not divisible by 9``````
``````#    Ruby program for
#    Number divisible by 9 using bitwise
class Divisibility
def divisibleBy9(num)
if (num == 9 || num == 0)
#  Base case when number is 0 or 9
return true
end
if (num < 9)
return false
end

#  Check divisibility of 9 using recursion
return self.divisibleBy9((num >> 3) - ((num & 7)))
end

end

def main()
num = 81
print("\n Number ", num ," divisible by 9")
else

print("\n Number ", num ," is not divisible by 9")
end

num = 56
print("\n Number ", num ," divisible by 9")
else

print("\n Number ", num ," is not divisible by 9")
end

end

main()``````

#### Output

`````` Number 81 divisible by 9
Number 56 is not divisible by 9``````
``````/*
Scala program for
Number divisible by 9 using bitwise
*/
class Divisibility()
{
def divisibleBy9(num: Int): Boolean = {
if (num == 9 || num == 0)
{
// Base case when number is 0 or 9
return true;
}
if (num < 9)
{
return false;
}
// Check divisibility of 9 using recursion
return divisibleBy9((num >> 3) - ((num & 7)));
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Divisibility = new Divisibility();
var num: Int = 81;
{
print("\n Number " + num + " divisible by 9");
}
else
{
print("\n Number " + num + " is not divisible by 9");
}
num = 56;
{
print("\n Number " + num + " divisible by 9");
}
else
{
print("\n Number " + num + " is not divisible by 9");
}
}
}``````

#### Output

`````` Number 81 divisible by 9
Number 56 is not divisible by 9``````
``````/*
Swift 4 program for
Number divisible by 9 using bitwise
*/
class Divisibility
{
func divisibleBy9(_ num: Int) -> Bool
{
if (num == 9 || num == 0)
{
// Base case when number is 0 or 9
return true;
}
if (num < 9)
{
return false;
}
// Check divisibility of 9 using recursion
return self.divisibleBy9((num >> 3) - ((num & 7)));
}
}
func main()
{
let task: Divisibility = Divisibility();
var num: Int = 81;
{
print("\n Number", num ,"divisible by 9", terminator: "");
}
else
{
print("\n Number", num ,"is not divisible by 9", terminator: "");
}
num = 56;
{
print("\n Number", num ,"divisible by 9", terminator: "");
}
else
{
print("\n Number", num ,"is not divisible by 9", terminator: "");
}
}
main();``````

#### Output

`````` Number 81 divisible by 9
Number 56 is not divisible by 9``````
``````/*
Kotlin program for
Number divisible by 9 using bitwise
*/
class Divisibility
{
fun divisibleBy9(num: Int): Boolean
{
if (num == 9 || num == 0)
{
// Base case when number is 0 or 9
return true;
}
if (num < 9)
{
return false;
}
// Check divisibility of 9 using recursion
return this.divisibleBy9((num shr 3) - ((num and 7)));
}
}
fun main(args: Array < String > ): Unit
{
val task: Divisibility = Divisibility();
var num: Int = 81;
{
print("\n Number " + num + " divisible by 9");
}
else
{
print("\n Number " + num + " is not divisible by 9");
}
num = 56;
{
print("\n Number " + num + " divisible by 9");
}
else
{
print("\n Number " + num + " is not divisible by 9");
}
}``````

#### Output

`````` Number 81 divisible by 9
Number 56 is not divisible by 9``````

## Resultant Output Explanation

For the given code, the output is as follows:

``````Number 81 divisible by 9
Number 56 is not divisible by 9``````
• The number 81 is divisible by 9, and the code correctly identifies it.
• The number 56 is not divisible by 9, and the code gives the correct result.

## Time Complexity

The time complexity of the code can be analyzed by looking at the number of recursive calls made. The input number `num` is right-shifted by 3 positions in each recursive call, which reduces its value significantly. The number of recursive calls can be approximated as O(log(num)), which makes the time complexity of the code O(log(num)). This recursive approach results in a relatively efficient algorithm for checking divisibility by 9 using bitwise operations.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post