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[])
{
int a = 37;
// b is power of 2
int b = 4;
a = 63;
// b is power of 2
b = 8;
}
}``````

#### 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()
{
int a = 37;
// b is power of 2
int b = 4;
a = 63;
// b is power of 2
b = 8;
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)
{
int a = 37;
// b is power of 2
int b = 4;
a = 63;
// b is power of 2
b = 8;
}
}``````

#### 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()
{
\$a = 37;
// b is power of 2
\$b = 4;
\$a = 63;
// b is power of 2
\$b = 8;
}
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 a = 37;
// b is power of 2
var b = 4;
a = 63;
// b is power of 2
b = 8;
}
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() :
a = 37
#  b is power of 2
b = 4
a = 63
#  b is power of 2
b = 8

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()
a = 37
#  b is power of 2
b = 4
a = 63
#  b is power of 2
b = 8
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;
a = 63;
// b is power of 2
b = 8;
}
}``````

#### 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()
{
var a: Int = 37;
// b is power of 2
var b: Int = 4;
a = 63;
// b is power of 2
b = 8;
}
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
{
var a: Int = 37;
// b is power of 2
var b: Int = 4;
a = 63;
// b is power of 2
b = 8;
}``````

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

Categories
Relative Post