Posted on by Kalkicode
Code Bit Logic

Compute modulus division by a power of 2 number

The problem at hand is to compute the modulus division of an integer by a power of 2 number. In other words, given an integer a and a power of 2 value b, the objective is to find the remainder when a is divided by b.

Problem Statement and Description

Modulus division is a mathematical operation that yields the remainder when one number is divided by another. When b is a power of 2 (e.g., 2, 4, 8, 16, etc.), an interesting property comes into play. Since powers of 2 are represented in binary as a sequence of 1 followed by zeros, subtracting 1 from b results in a sequence of binary ones. This property can be exploited to efficiently compute the modulus division without actually performing the division operation.

For instance, let's take a = 37 and b = 4 as an example. In binary representation, 4 is 100, and 3 is 011. When we perform bitwise AND operation between a and b - 1, we are effectively masking out the higher order bits of a which are multiples of b and retaining only the lower bits that represent the remainder. In this case, 37 & (4 - 1) results in 1, which is the remainder when 37 is divided by 4.

Idea to Solve the Problem

The key insight here is that when b is a power of 2, b - 1 has all its lower bits set to 1. Therefore, performing bitwise AND operation between a and b - 1 is equivalent to isolating the lower bits of a, which corresponds to the remainder.

Standard Pseudocode

procedure modulusDivision(a: integer, b: integer)
    ans1 = a % b
    ans2 = a & (b - 1)
    print("Using modulus:", a, "%", b, "=", ans1)
    print("Using bitwise:", a, "&", "(", b, "-", 1, ")", "=", ans2)
end procedure

Algorithm Explanation

  1. Start with the given integers a and b, where b is a power of 2.
  2. Calculate ans1 by performing a % b, which gives the remainder when a is divided by b.
  3. Calculate ans2 by performing a & (b - 1). The bitwise AND operation isolates the lower bits of a that correspond to the remainder when divided by b.
  4. Print the results of both computations to show that both methods yield the same remainder.

Code Solution

/*
    C program for
    Compute modulus division by a power of 2 number
*/
#include <stdio.h>

void modulusDivision(int a, int b)
{
	printf("\n Given a : %d b %d ", a, b);
	// Assume b is power of 2
	// Case A Using modulus operator
	int ans1 = a % b;
	printf("\n Using modulus :  (%d  %%  %d) = %d", a, b, ans1);
	// Case A Using bitwise operator
	int ans2 = a & (b - 1);
	printf("\n Using bitwise :  (%d & (%d - 1)) = %d\n", a, b, ans2);
}
int main()
{
	int a = 37;
	// b is power of 2
	int b = 4;
	modulusDivision(a, b);
	a = 63;
	// b is power of 2
	b = 8;
	modulusDivision(a, b);
	return 0;
}

Output

 Given a : 37 b 4
 Using modulus :  (37  %  4) = 1
 Using bitwise :  (37 & (4 - 1)) = 1

 Given a : 63 b 8
 Using modulus :  (63  %  8) = 7
 Using bitwise :  (63 & (8 - 1)) = 7
// Java Program 
// Compute modulus division by a power of 2 number
public class Division
{
	public void modulusDivision(int a, int b)
	{
		System.out.print("\n Given a : " + 
                         a + " b : " + b);
		// Assume b is power of 2
		// Case A Using modulus operator
		int ans1 = a % b;
		System.out.print("\n Using modulus : (" + 
                         a + " % " + b + ") = " + ans1);
		// Case A Using bitwise operator
		int ans2 = a & (b - 1);
		System.out.println("\n Using bitwise : (" + 
                           a + " & (" + b + " - 1)) = " + ans2);
	}
	public static void main(String args[])
	{
		Division task = new Division();
		int a = 37;
		// b is power of 2
		int b = 4;
		task.modulusDivision(a, b);
		a = 63;
		// b is power of 2
		b = 8;
		task.modulusDivision(a, b);
	}
}

Output

 Given a : 37 b : 4
 Using modulus : (37 % 4) = 1
 Using bitwise : (37 & (4 - 1)) = 1

 Given a : 63 b : 8
 Using modulus : (63 % 8) = 7
 Using bitwise : (63 & (8 - 1)) = 7
// Include header file
#include <iostream>
using namespace std;
// C++ Program 
// Compute modulus division by a power of 2 number
class Division
{
	public: void modulusDivision(int a, int b)
	{
		cout << "\n Given a : " << a << " b : " << b;
		// Assume b is power of 2
		// Case A Using modulus operator
		int ans1 = a % b;
		cout << "\n Using modulus : (" 
      		 << a << " % " << b << ") = " 
      		<< ans1;
		// Case A Using bitwise operator
		int ans2 = a &(b - 1);
		cout << "\n Using bitwise : (" 
      		 << a << " &(" << b << " - 1)) = " 
              << ans2 << endl;
	}
};
int main()
{
	Division *task = new Division();
	int a = 37;
	// b is power of 2
	int b = 4;
	task->modulusDivision(a, b);
	a = 63;
	// b is power of 2
	b = 8;
	task->modulusDivision(a, b);
	return 0;
}

Output

 Given a : 37 b : 4
 Using modulus : (37 % 4) = 1
 Using bitwise : (37 &(4 - 1)) = 1

 Given a : 63 b : 8
 Using modulus : (63 % 8) = 7
 Using bitwise : (63 &(8 - 1)) = 7
// Include namespace system
using System;
// Csharp Program 
// Compute modulus division by a power of 2 number
public class Division
{
	public void modulusDivision(int a, int b)
	{
		Console.Write("\n Given a : " + a + " b : " + b);
		// Assume b is power of 2
		// Case A Using modulus operator
		int ans1 = a % b;
		Console.Write("\n Using modulus : (" + 
                      a + " % " + b + ") = " + ans1);
		// Case A Using bitwise operator
		int ans2 = a & (b - 1);
		Console.WriteLine("\n Using bitwise : (" + 
                          a + " & (" + b + " - 1)) = " + ans2);
	}
	public static void Main(String[] args)
	{
		Division task = new Division();
		int a = 37;
		// b is power of 2
		int b = 4;
		task.modulusDivision(a, b);
		a = 63;
		// b is power of 2
		b = 8;
		task.modulusDivision(a, b);
	}
}

Output

 Given a : 37 b : 4
 Using modulus : (37 % 4) = 1
 Using bitwise : (37 & (4 - 1)) = 1

 Given a : 63 b : 8
 Using modulus : (63 % 8) = 7
 Using bitwise : (63 & (8 - 1)) = 7
<?php
// Php Program 
// Compute modulus division by a power of 2 number
class Division
{
	public	function modulusDivision($a, $b)
	{
		echo("\n Given a : ".$a.
			" b : ".$b);
		// Assume b is power of 2
		// Case A Using modulus operator
		$ans1 = $a % $b;
		echo("\n Using modulus : (".$a.
			" % ".$b.
			") = ".$ans1);
		// Case A Using bitwise operator
		$ans2 = $a & ($b - 1);
		echo("\n Using bitwise : (".$a.
			" & (".$b.
			" - 1)) = ".$ans2.
			"\n");
	}
}

function main()
{
	$task = new Division();
	$a = 37;
	// b is power of 2
	$b = 4;
	$task->modulusDivision($a, $b);
	$a = 63;
	// b is power of 2
	$b = 8;
	$task->modulusDivision($a, $b);
}
main();

Output

 Given a : 37 b : 4
 Using modulus : (37 % 4) = 1
 Using bitwise : (37 & (4 - 1)) = 1

 Given a : 63 b : 8
 Using modulus : (63 % 8) = 7
 Using bitwise : (63 & (8 - 1)) = 7
package main
import "fmt"
// Go Program 
// Compute modulus division by a power of 2 number

func modulusDivision(a, b int) {
	fmt.Print("\n Given a : ", a, " b : ", b)
	// Assume b is power of 2
	// Case A Using modulus operator
	var ans1 int = a % b
	fmt.Print("\n Using modulus : (", a, " % ", b, ") = ", ans1)
	// Case A Using bitwise operator
	var ans2 int = a & (b - 1)
	fmt.Println("\n Using bitwise : (", a, " & (", b, " - 1)) = ", ans2)
}
func main() {
	
	var a int = 37
	// b is power of 2
	var b int = 4
	modulusDivision(a, b)
	a = 63
	// b is power of 2
	b = 8
	modulusDivision(a, b)
}

Output

 Given a : 37 b : 4
 Using modulus : (37 % 4) = 1
 Using bitwise : (37 & (4 - 1)) = 1

 Given a : 63 b : 8
 Using modulus : (63 % 8) = 7
 Using bitwise : (63 & (8 - 1)) = 7
// Node JS Program 
// Compute modulus division by a power of 2 number
class Division
{
	modulusDivision(a, b)
	{
		process.stdout.write("\n Given a : " + a + " b : " + b);
		// Assume b is power of 2
		// Case A Using modulus operator
		var ans1 = a % b;
		process.stdout.write("\n Using modulus : (" + 
                             a + " % " + b + ") = " + ans1);
		// Case A Using bitwise operator
		var ans2 = a & (b - 1);
		console.log("\n Using bitwise : (" + 
                    a + " & (" + b + " - 1)) = " + ans2);
	}
}

function main()
{
	var task = new Division();
	var a = 37;
	// b is power of 2
	var b = 4;
	task.modulusDivision(a, b);
	a = 63;
	// b is power of 2
	b = 8;
	task.modulusDivision(a, b);
}
main();

Output

 Given a : 37 b : 4
 Using modulus : (37 % 4) = 1
 Using bitwise : (37 & (4 - 1)) = 1

 Given a : 63 b : 8
 Using modulus : (63 % 8) = 7
 Using bitwise : (63 & (8 - 1)) = 7
#  Python 3 Program 
#  Compute modulus division by a power of 2 number
class Division :
	def modulusDivision(self, a, b) :
		print("\n Given a : ", a ," b : ", b, end = "")
		#  Assume b is power of 2
		#  Case A Using modulus operator
		ans1 = a % b
		print("\n Using modulus : (", a ," % ", b ,") = ", ans1, end = "")
		#  Case A Using bitwise operator
		ans2 = a & (b - 1)
		print("\n Using bitwise : (", a ," & (", b ," - 1)) = ", ans2)
	

def main() :
	task = Division()
	a = 37
	#  b is power of 2
	b = 4
	task.modulusDivision(a, b)
	a = 63
	#  b is power of 2
	b = 8
	task.modulusDivision(a, b)

if __name__ == "__main__": main()

Output

 Given a :  37  b :  4
 Using modulus : ( 37  %  4 ) =  1
 Using bitwise : ( 37  & ( 4  - 1)) =  1

 Given a :  63  b :  8
 Using modulus : ( 63  %  8 ) =  7
 Using bitwise : ( 63  & ( 8  - 1)) =  7
#  Ruby Program 
#  Compute modulus division by a power of 2 number
class Division 
	def modulusDivision(a, b) 
		print("\n Given a : ", a ," b : ", b)
		#  Assume b is power of 2
		#  Case A Using modulus operator
		ans1 = a % b
		print("\n Using modulus : (", a ," % ", b ,") = ", ans1)
		#  Case A Using bitwise operator
		ans2 = a & (b - 1)
		print("\n Using bitwise : (", a ," & (", b ," - 1)) = ", ans2, "\n")
	end

end

def main() 
	task = Division.new()
	a = 37
	#  b is power of 2
	b = 4
	task.modulusDivision(a, b)
	a = 63
	#  b is power of 2
	b = 8
	task.modulusDivision(a, b)
end

main()

Output

 Given a : 37 b : 4
 Using modulus : (37 % 4) = 1
 Using bitwise : (37 & (4 - 1)) = 1

 Given a : 63 b : 8
 Using modulus : (63 % 8) = 7
 Using bitwise : (63 & (8 - 1)) = 7

// Scala Program 
// Compute modulus division by a power of 2 number
class Division()
{
	def modulusDivision(a: Int, b: Int): Unit = {
		print("\n Given a : " + a + " b : " + b);
		// Assume b is power of 2
		// Case A Using modulus operator
		var ans1: Int = a % b;
		print("\n Using modulus : (" + a + " % " + b + ") = " + ans1);
		// Case A Using bitwise operator
		var ans2: Int = a & (b - 1);
		println("\n Using bitwise : (" + a + " & (" + b + " - 1)) = " + ans2);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Division = new Division();
		var a: Int = 37;
		// b is power of 2
		var b: Int = 4;
		task.modulusDivision(a, b);
		a = 63;
		// b is power of 2
		b = 8;
		task.modulusDivision(a, b);
	}
}

Output

 Given a : 37 b : 4
 Using modulus : (37 % 4) = 1
 Using bitwise : (37 & (4 - 1)) = 1

 Given a : 63 b : 8
 Using modulus : (63 % 8) = 7
 Using bitwise : (63 & (8 - 1)) = 7
// Swift 4 Program 
// Compute modulus division by a power of 2 number
class Division
{
	func modulusDivision(_ a: Int, _ b: Int)
	{
		print("\n Given a : ", a ," b : ", b, terminator: "");
		// Assume b is power of 2
		// Case A Using modulus operator
		let ans1: Int = a % b;
		print("\n Using modulus : (", a ," % ", b ,") = ", 
              ans1, terminator: "");
		// Case A Using bitwise operator
		let ans2: Int = a & (b - 1);
		print("\n Using bitwise : (", a ," & (", b ," - 1)) = ", ans2);
	}
}
func main()
{
	let task: Division = Division();
	var a: Int = 37;
	// b is power of 2
	var b: Int = 4;
	task.modulusDivision(a, b);
	a = 63;
	// b is power of 2
	b = 8;
	task.modulusDivision(a, b);
}
main();

Output

 Given a :  37  b :  4
 Using modulus : ( 37  %  4 ) =  1
 Using bitwise : ( 37  & ( 4  - 1)) =  1

 Given a :  63  b :  8
 Using modulus : ( 63  %  8 ) =  7
 Using bitwise : ( 63  & ( 8  - 1)) =  7
// Kotlin Program 
// Compute modulus division by a power of 2 number
class Division
{
	fun modulusDivision(a: Int, b: Int): Unit
	{
		print("\n Given a : " + a + " b : " + b);
		// Assume b is power of 2
		// Case A Using modulus operator
		val ans1: Int = a % b;
		print("\n Using modulus : (" + a + " % " + b + ") = " + ans1);
		// Case A Using bitwise operator
		val ans2: Int = a and(b - 1);
		println("\n Using bitwise : (" + a + " & (" + b + " - 1)) = " + ans2);
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Division = Division();
	var a: Int = 37;
	// b is power of 2
	var b: Int = 4;
	task.modulusDivision(a, b);
	a = 63;
	// b is power of 2
	b = 8;
	task.modulusDivision(a, b);
}

Output

 Given a : 37 b : 4
 Using modulus : (37 % 4) = 1
 Using bitwise : (37 & (4 - 1)) = 1

 Given a : 63 b : 8
 Using modulus : (63 % 8) = 7
 Using bitwise : (63 & (8 - 1)) = 7

Time Complexity

The time complexity of this approach is constant, O(1), for both calculations. This is because the operations involve simple arithmetic calculations and bitwise operations, which execute in a constant amount of time regardless of the magnitude of the input numbers.

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





Categories
Relative Post