Compute n modulo d without division(/) and modulo(%) operators, where d is a power of 2 number.
Input: 6 4
Output: 2
Explanation: As 6%4 = 2
Input: 12 8
Output: 4
Explanation: As 12%8 = 4
Input: 10 2
Output: 0
Explanation:As 10%2 = 0
Let ith bit from right is set in d. For getting n modulus d, we just need to return 0 to i-1 (from right) bits of n as they are and other bits as 0.
For example if n = 6 (00..110) and d = 4(00..100). Last set bit in d is at position 3 (from right side). So we need to return last two bits of n as they are and other bits as 0, i.e., 00..010.
Now doing it is so easy, guess it….
Yes, you have guessing it right. See the below program.
C
#include<stdio.h>
unsigned int getModulo(unsigned int n,
unsigned int d)
{
return ( n & (d - 1) );
}
int main()
{
unsigned int n = 6;
unsigned int d = 4;
printf("%u modulo %u is %u", n, d, getModulo(n, d));
getchar();
return 0;
}
|
C++
#include<iostream>
using namespace std;
unsigned int getModulo(unsigned int n,
unsigned int d)
{
return ( n & (d - 1) );
}
int main()
{
unsigned int n = 6;
unsigned int d = 4;
cout<< n <<" modulo "<<d <<" is "<< getModulo(n, d);
getchar();
return 0;
}
|
Java
import java.io.*;
public class GFG {
static int getModulo(int n, int d)
{
return ( n & (d-1) );
}
public static void main(String[] args)
{
int n = 6;
int d = 4;
System.out.println(n+" modulo " + d +
" is " + getModulo(n, d));
}
}
|
Python3
def getModulo(n, d):
return ( n & (d-1) )
n = 6
d = 4
print(n,"modulo",d,"is",
getModulo(n, d))
|
Javascript
<script>
function getModulo(n,d)
{
return ( n & (d - 1) );
}
n = 6;
d = 4;
document.write(n +" modulo "+ d + " is "+ getModulo(n, d));
</script>
|
C#
using System;
class GFG {
static uint getModulo( uint n, uint d)
{
return ( n & (d-1) );
}
static public void Main ()
{
uint n = 6;
uint d = 4;
Console.WriteLine( n + " modulo " + d +
" is " + getModulo(n, d));
}
}
|
PHP
<?php
function getModulo($n, $d)
{
return ( $n & ($d - 1) );
}
$n = 6;
$d = 4;
echo $n ," modulo"," ", $d, " is ",
" ",getModulo($n, $d);
?>
|
Time Complexity: O(1), As we are doing single operation which takes constant time.
Auxiliary Space: O(1), As constant extra space is used.
Another Approach:
- Read in the values of n and d from the user.
- Subtract 1 from d to get a number with all bits set to 1 up to the position of the highest set bit in d. This is called the mask.
- Perform a bitwise AND of n and the mask to get the remainder. This will give us the last i bits of n where i is the position of the highest set bit in d.
- Output the result.
C++
#include <iostream>
using namespace std;
int main()
{
int n, d;
n = 6;
d = 4;
int mask = d - 1;
int result = n & mask;
cout << result << endl;
return 0;
}
|
Java
import java.io.*;
public class Main {
public static void main(String[] args) {
int n, d;
n = 6;
d = 4;
int mask = d - 1;
int result = n & mask;
System.out.println(result);
}
}
|
Javascript
let n, d;
n = 6;
d = 4;
let mask = d - 1;
let result = n & mask;
document.write(result);
|
C#
using System;
class Program
{
static void Main(string[] args)
{
int n, d;
n = 6;
d = 4;
int mask = d - 1;
int result = n & mask;
Console.WriteLine(result);
Console.ReadLine();
}
}
|
Python3
n = 6
d = 4
mask = d - 1
result = n & mask
print(result)
|
Time Complexity: O(1)
Auxiliary Space: O(1)
References:
http://graphics.stanford.edu/~seander/bithacks.html#ModulusDivisionEasy
Please write comments if you find any bug in the above program/algorithm or other ways to solve the same problem.
