Tutorialspoint.dev

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

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

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

Input : x = 4, y = 14
Output : 14
Explanation : 14 % 24 =  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 2x is greater than long long int range, we can not obtain proper result.
  • Whenever y < 2x the remainder will always be y. So, in that case we can restrict ourselves to calculate value of 2x as:
    y < 2x
    log y < x
    // means if log y is less than x, then 
    // we can print y as remainder.
  • The maximum value of 2x for which we can store 2x in a variable is 263. This means for x > 63, y is always going to be smaller than 2x and in that case remainder of y mod 2x 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;
}

Python

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

/div>

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)

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)
?>


Output:

57

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



This article is attributed to GeeksforGeeks.org

You Might Also Like

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter