商和余数除以2^k（2的幂）-yiteyi-C++库

给你一个正整数n作为被除数，另一个数字m（2^k的形式），你必须找到商和余数，而不需要进行实际除法。例如：

null

Input : n = 43, m = 8Output : Quotient = 5, Remainder = 3Input : n = 58, m = 16Output : Quotient = 3, Remainder = 10

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

在本文中，我们使用数字的逐位表示来理解任何数字被形式为2^k的除数除法的作用。所有二的幂的数字在其表示中只包含1个集合位，我们将使用这个属性。为了求余数，我们将取被除数（n）和除数减1（m-1）的逻辑AND，这将只给除数的集合位赋予除数的集合位，在这种情况下，它是我们的实际余数。此外，被除数的左半部分（从除数中设置位的位置）将被视为商。因此，从被除数（n）中，从除数的设定位的位置移除所有位将得到商，右移位被除数log2（m）次将完成求商的工作。

余数=n&（m-1）
商=（n>>log2（m））

注：Log2（m）将给出m的二进制表示中存在的位数。

图片[1]-商和余数除以2^k（2的幂）-yiteyi-C++库

C++

                         // CPP to find remainder and quotient                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // function to print remainder and quotient                       
                         void                                     divide(                                     int                                     n,                                     int                                     m)                       
                         {                       
                                                 // print Remainder by                       
                                                 // n AND (m-1)                       
                                                 cout <<                                     "Remainder = "                                     << ((n) &(m-1));                       
                                   
                                                 // print quotient by                       
                                                 // right shifting n by (log2(m)) times                       
                                                 cout <<                                     "Quotient = "                                     <<(n >> (                                     int                                     )(log2(m)));                       
                                   
                         }                       
           
                         // driver program                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 43, m = 8;                       
                                                 divide(n, m);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java to find remainder and quotient                       
                         import                                     java.io.*;                       
           
                         public                                     class                                     GFG {                       
                                   
                                                 // function to print remainder and                       
                                                 // quotient                       
                                                 static                                     void                                     divide(                                     int                                     n,                                     int                                     m)                       
                                                 {                       
                                   
                                                 // print Remainder by                       
                                                 // n AND (m-1)                       
                                                 System.out.println(                                     "Remainder = "                       
                                                 + ((n) &(m-                                     1                                     )));                       
                                   
                                                 // print quotient by right shifting                       
                                                 // n by (log2(m)) times                       
                                                 System.out.println(                                     "Quotient = "                       
                                                 + (n >> (                                     int                                     )(Math.log(m) / Math.log(                                     2                                     ))));                       
                                                 }                       
                                   
                                                 // driver program                       
                                                 static                                     public                                     void                                     main (String[] args)                       
                                                 {                       
                                                 int                                     n =                                     43                                     , m =                                     8                                     ;                       
                                   
                                                 divide(n, m);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by vt_m.                       

Python 3

                         # Python 3 to find remainder and                       
                         # quotient                       
                         import                                     math                       
                         # function to print remainder and                       
                         # quotient                       
                         def                                     divide(n, m):                       
           
                                                 # print Remainder by                       
                                                 # n AND (m-1)                       
                                                 print                                     (                                     "Remainder = "                                     ,                       
                                                 ((n) &(m                                     -                                     1                                     )))                       
                                   
                                                 # print quotient by                       
                                                 # right shifting n by                       
                                                 # (log2(m)) times                       
                                                 print                                     (                                     "Quotient = "                                     ,(n >>                       
                                                 (                                     int                                     )(math.log2(m))))                       
           
                         # driver program                       
                         n                                     =                                     43                       
                         m                                     =                                     8                       
                         divide(n, m)                       
           
                         # This code is contributed by                       
                         # Smitha                       

C#

                         // C# to find remainder and quotient                       
                         using                                     System;                       
           
                         public                                     class                                     GFG                       
                         {                       
                                                 // function to print remainder and quotient                       
                                                 static                                     void                                     divide(                                     int                                     n,                                     int                                     m)                       
                                                 {                       
                                                 // print Remainder by                       
                                                 // n AND (m-1)                       
                                                 Console.WriteLine(                                     "Remainder = "                                     +((n) & (m - 1)));                       
                                   
                                                 // print quotient by                       
                                                 // right shifting n by (log2(m)) times                       
                                                 Console.WriteLine(                                     "Quotient = "                       
                                                 + (n >> (                                     int                                     )(Math.Log(m))));                       
                                   
                                                 }                       
                                   
                                                 // Driver program                       
                                                 static                                     public                                     void                                     Main ()                       
                                                 {                       
                                                 int                                     n = 43, m = 8;                       
                                                 divide(n, m);                       
                                   
                                                 }                       
                         }                       
           
                         // This code is contributed by vt_m.                       

PHP

                         <?php                       
                         // PHP Code to find remainder                       
                         // and quotient                       
           
                         // function to print remainder                       
                         // and quotient                       
                         function                                     divide(                                     $n                                     ,                                     $m                                     )                       
                         {                       
                                   
                                                 // print Remainder by                       
                                                 // n AND (m-1)                       
                                                 echo                                     "Remainder = "                                     . ((                                     $n                                     ) &(                                     $m                                     - 1));                       
                                   
                                                 // print quotient by                       
                                                 // right shifting n by                       
                                                 // (log(m,2)) times 2                       
                                                 // is base                       
                                                 echo                                     "Quotient = "                                     .(                                     $n                                     >> (int)(log(                                     $m                                     , 2)));                       
           
                         }                       
           
                                                 // Driver Code                       
                                                 $n                                     = 43;                       
                                                 $m                                     = 8;                       
                                                 divide(                                     $n                                     ,                                     $m                                     );                       
           
                         //This code is contributed by mits                       
                         ?>                       

Javascript

                         <script>                       
                         // javascript program to find last index                       
                         // of character x in given string.                       
           
                                                 // function to print remainder and                       
                                                 // quotient                       
                                                 function                                     divide(n, m)                       
                                                 {                       
                                   
                                                 // print Remainder by                       
                                                 // n AND (m-1)                       
                                                 document.write(                                     "Remainder = "                       
                                                 + ((n) &(m-1)) +                                     "<br/>"                                     );                       
                                   
                                                 // print quotient by right shifting                       
                                                 // n by (log2(m)) times                       
                                                 document.write(                                     "Quotient = "                       
                                                 + (n >> (Math.log(m) / Math.log(2))));                       
                                                 }                       
                                   
                         // Driver code                       
                                                 let n = 43, m = 8;                       
                                                 divide(n, m);                       
                                   
                                                 // This code is contributed by sanjoy_62.                       
                         </script>                       

输出：

Remainder = 3Quotient = 5

时间复杂度：O（1） 辅助空间：O（1）

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章