Skip to main content

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;
		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.

Last updated on by Kalkicode




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.

New Comment