Find value of y mod (2 raised to power x)

0 0 5 minutes read

Given two positive integer x and y. we have to find the value of y mod 2^x. That is remainder when y is divided by 2^x.

Examples:

Input : x = 3, y = 14
Output : 6
Explanation : 14 % 2³ =  14 % 8 = 6.

Input : x = 4, y = 14
Output : 14
Explanation : 14 % 2⁴ =  14 % 16 = 14.

To solve this question we can use pow() and modulo operator and can easily find the remainder.
But there are some points we should care about:

For higher value of x such that 2^x is greater than long long int range, we can not obtain proper result.
Whenever y < 2^x the remainder will always be y. So, in that case we can restrict ourselves to calculate value of 2^x as:

y < 2^x
log y < x
// means if log y is less than x, then 
// we can print y as remainder.

The maximum value of 2^x for which we can store 2^x in a variable is 2⁶³. This means for x > 63, y is always going to be smaller than 2^x and in that case remainder of y mod 2^x is y itself.

keeping in mind the above points we can approach this problem as :

if (log y < x)
    return y;
else if (x  < 63)
    return y;
else 
    return (y % (pow(2, x)))

Note: As python is limit free we can directly use mod and pow() function

C++

// C++ Program to find the 
// value of y mod 2^x
#include <bits/stdc++.h>
using namespace std;
 
// function to calculate y mod 2^x
long long int yMod(long long int y,
                    long long int x)
{
    // case 1 when y < 2^x
    if (log2(y) < x)
        return y;
 
    // case 2 when 2^x is out of 
    // range means again y < 2^x
    if (x > 63)
        return y;
 
    // if y > 2^x
    return (y % (1 << x));
}
 
// driver program
int main()
{
    long long int y = 12345;
    long long int x = 11;    
    cout << yMod(y, x);    
    return 0;
}

Java

// Java Program to find 
// the value of y mod 2^x
import java.io.*;
 
class GFG
{
    // function to calculate
    // y mod 2^x
    static long yMod(long y,    
                     long x)
    {
        // case 1 when y < 2^x
        if ((Math.log(y) / 
             Math.log(2)) < x)
            return y;
     
        // case 2 when 2^x is 
        // out of range means 
        // again y < 2^x
        if (x > 63)
            return y;
     
        // if y > 2^x
        return (y % (1 << (int)x));
    }
     
    // Driver Code
    public static void main(String args[])
    {
        long y = 12345;
        long x = 11; 
        System.out.print(yMod(y, x)); 
    }
}
 
// This code is contributed by 
// Manish Shaw(manishshaw1)

Python3

# Program to find the value 
# of y mod 2 ^ x function to 
# return y mod 2 ^ x
def yMod(y, x) :     
    return (y % pow(2, x))   
      
# Driver code
y = 12345
x = 11
print(yMod(y, x))

C#

// C# Program to find the 
// value of y mod 2^x
using System;
 
class GFG
{
    // function to calculate
    // y mod 2^x
    static long yMod(long y, 
                     long x)
    {
        // case 1 when y < 2^x
        if (Math.Log(y, 2) < x)
            return y;
     
        // case 2 when 2^x is 
        // out of range means 
        // again y < 2^x
        if (x > 63)
            return y;
     
        // if y > 2^x
        return (y % (1 << (int)x));
    }
     
    // Driver Code
    static void Main()
    {
        long y = 12345;
        long x = 11; 
        Console.Write(yMod(y, x)); 
    }
}
 
// This code is contributed by 
// Manish Shaw(manishshaw1)

PHP

<?php
// PHP Program to find the 
// value of y mod 2^x
 
// function to 
// calculate y mod 2^x
function yMod($y, $x)
{
    // case 1 when y < 2^x
    if ((log($y) / log(2)) < $x)
        return $y;
 
    // case 2 when 2^x is
    // out of range means 
    // again y < 2^x
    if ($x > 63)
        return $y;
 
    // if y > 2^x
    return ($y % (1 << $x));
}
 
// Driver Code
$y = 12345;
$x = 11; 
echo (yMod($y, $x)); 
 
// This code is contributed by 
// Manish Shaw(manishshaw1)
?>

Javascript

<script>
 
// Javascript program to find the
// value of y mod 2^x
 
// Function to calculate y mod 2^x
function yMod(y, x)
{
     
    // Case 1 when y < 2^x
    if ((Math.log(y) / Math.log(2)) < x)
        return y;
 
    // Case 2 when 2^x is
    // out of range means
    // again y < 2^x
    if (x > 63)
        return y;
 
    // If y > 2^x
    return (y % (1 << x));
}
 
// Driver Code
let y = 12345;
let x = 11;
 
document.write(yMod(y, x));
 
// This code is contributed by _saurabh_jaiswal
 
</script>

Output

Time Complexity: O(x)
Auxiliary Space: O(1)

Approach: Bitwise manipulation

This approach is called bitwise manipulation. Here are the steps:

Calculate 2^x using the left shift operator (<<). For example, 1 << 3 will give us 8.
Subtract 1 from the result of step 1 to get a binary number with x number of 1’s. For example, 2^3 – 1 = 7, which in binary is 111.
Perform a bitwise AND operation between y and the result of step 2. The result will be the remainder when y is divided by 2^x.

C++

#include <iostream>
 
int find_modulo(int x, int y)
{
    int result = y & ((1 << x) - 1);
    std::cout << "The remainder of " << y << " when divided by 2^" << x << " is " << result << "." << std::endl;
    return result;
}
 
int main()
{
    find_modulo(3, 14);
    find_modulo(4, 14);
    return 0;
}

Java

public class Main {
    public static int find_modulo(int x, int y) {
        int result = y & ((1 << x) - 1);
        System.out.println("The remainder of " + y + " when divided by 2^" + x + " is " + result + ".");
        return result;
    }
 
    public static void main(String[] args) {
        find_modulo(3, 14);
        find_modulo(4, 14);
    }
}

Python3

def find_modulo(x, y):
    result = y & ((1 << x) - 1)
    print(f"The remainder of {y} when divided by 2^{x} is {result}.")
    return result
 
find_modulo(3, 14)
find_modulo(4, 14)

C#

using System;
 
class Program {
    static int FindModulo(int x, int y) {
        int result = y & ((1 << x) - 1);
        Console.WriteLine($"The remainder of {y} when divided by 2^{x} is {result}.");
        return result;
    }
    // Drive code 
    static void Main(string[] args) {
        FindModulo(3, 14);
        FindModulo(4, 14);
    }
}
// This code is contributed by Shiv1o43g

Javascript

// Javascript program to find remainder of y when divided by 2^x
function findModulo(x, y) {
let result = y & ((1 << x) - 1);
console.log(The remainder of ${y} when divided by 2^${x} is ${result}.);
return result;
}
 
// Driver code
findModulo(3, 14);
findModulo(4, 14);

Output

The remainder of 14 when divided by 2^3 is 6.
The remainder of 14 when divided by 2^4 is 14.

The time complexity: O(1)
The auxiliary space: O(1)

Compute modulus division by a power-of-2-number

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!