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^xlong 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 programint 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^ximport 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 ^ xdef yMod(y, x) : return (y % pow(2, x)) # Driver codey = 12345x = 11print(yMod(y, x)) |
C#
// C# Program to find the // value of y mod 2^xusing 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^xfunction 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^xfunction 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 Codelet y = 12345;let x = 11;document.write(yMod(y, x));// This code is contributed by _saurabh_jaiswal</script> |
Output
57
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 resultfind_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^xfunction 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 codefindModulo(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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Find More to that Topic: geeksforgeeks.org/find-value-of-y-mod-2-raised-to-power-x/ […]