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:
-
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. -
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
- The function takes a number
num
as input. - If
num
is 9 or 0, it returns true (base case). - If
num
is less than 9, it returns false (base case). - The function calculates the new number as
(num >> 3) - (num & 7)
.(num >> 3)
shifts the bits ofnum
three positions to the right (equivalent to dividing by 8).(num & 7)
extracts the three least significant bits ofnum
.- The difference of the two gives a new number.
- The function makes a recursive call with the new number as the input.
- Steps 2 to 5 continue until a base case is reached.
- 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;
if (task.divisibleBy9(num))
{
System.out.print("\n Number " + num + " divisible by 9");
}
else
{
System.out.print("\n Number " + num + " is not divisible by 9");
}
num = 56;
if (task.divisibleBy9(num))
{
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;
if (task->divisibleBy9(num))
{
cout << "\n Number " << num << " divisible by 9";
}
else
{
cout << "\n Number " << num << " is not divisible by 9";
}
num = 56;
if (task->divisibleBy9(num))
{
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;
if (task.divisibleBy9(num))
{
Console.Write("\n Number " + num + " divisible by 9");
}
else
{
Console.Write("\n Number " + num + " is not divisible by 9");
}
num = 56;
if (task.divisibleBy9(num))
{
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;
if ($task->divisibleBy9($num))
{
echo("\n Number ".$num.
" divisible by 9");
}
else
{
echo("\n Number ".$num.
" is not divisible by 9");
}
$num = 56;
if ($task->divisibleBy9($num))
{
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;
if (task.divisibleBy9(num))
{
process.stdout.write("\n Number " + num + " divisible by 9");
}
else
{
process.stdout.write("\n Number " + num + " is not divisible by 9");
}
num = 56;
if (task.divisibleBy9(num))
{
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() :
task = Divisibility()
num = 81
if (task.divisibleBy9(num)) :
print("\n Number", num ,"divisible by 9", end = "")
else :
print("\n Number", num ,"is not divisible by 9", end = "")
num = 56
if (task.divisibleBy9(num)) :
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()
task = Divisibility.new()
num = 81
if (task.divisibleBy9(num))
print("\n Number ", num ," divisible by 9")
else
print("\n Number ", num ," is not divisible by 9")
end
num = 56
if (task.divisibleBy9(num))
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;
if (task.divisibleBy9(num))
{
print("\n Number " + num + " divisible by 9");
}
else
{
print("\n Number " + num + " is not divisible by 9");
}
num = 56;
if (task.divisibleBy9(num))
{
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;
if (task.divisibleBy9(num))
{
print("\n Number", num ,"divisible by 9", terminator: "");
}
else
{
print("\n Number", num ,"is not divisible by 9", terminator: "");
}
num = 56;
if (task.divisibleBy9(num))
{
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;
if (task.divisibleBy9(num))
{
print("\n Number " + num + " divisible by 9");
}
else
{
print("\n Number " + num + " is not divisible by 9");
}
num = 56;
if (task.divisibleBy9(num))
{
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.
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.
New Comment