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
- Start with the given integers
a
andb
, whereb
is a power of 2. - Calculate
ans1
by performinga % b
, which gives the remainder whena
is divided byb
. - Calculate
ans2
by performinga & (b - 1)
. The bitwise AND operation isolates the lower bits ofa
that correspond to the remainder when divided byb
. - 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.
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