算法题：如何计算模数除以2的幂？

本文概述

• C ++
• Java
• Python3
• C#
• 的PHP

在不使用除(/)和模(%)运算符的情况下计算n模d, 其中d是2的幂。

设d为右第i位，为了得到d的n个模量，我们只需要返回n的0到i-1位(从右)，其他位为0。

例如n = 6(00..110)和d = 4(00..100)。d中的最后一个设置位位于位置3(从右侧开始)。所以我们需要返回n的最后两位，其他的位为0，即00..010。

现在做起来非常容易, 猜出来……。

是的, 你猜对了。请参阅以下程序。

C ++

#include<stdio.h>
  
// This function will return n % d.
// d must be one of: 1, 2, 4, 8, 16, 32, … 
unsigned int getModulo(unsigned int n, unsigned int d)
{
return ( n & (d - 1) );
}         
  
// Driver Code
int main()
{
unsigned int n = 6;
  
// d must be a power of 2
unsigned int d = 4; 
printf ( "%u moduo %u is %u" , n, d, getModulo(n, d));
  
getchar ();
return 0;
}

Java

// Java code for Compute modulus division by 
// a power-of-2-number
class GFG {
      
     // This function will return n % d.
     // d must be one of: 1, 2, 4, 8, 16, 32, static int getModulo( int n, int d)
     {
         return ( n & (d- 1 ) );
     }     
      
     // Driver Code
     public static void main(String[] args)
     {
         int n = 6 ;
          
         /*d must be a power of 2*/
         int d = 4 ; 
          
         System.out.println(n+ " moduo " + d + 
                     " is " + getModulo(n, d));
     }
} 
  
// This code is contributed 
// by Smitha Dinesh Semwal.

Python3

# Python code to demonstrate
# modulus division by power of 2
  
  
# This function will
# return n % d.
# d must be one of:
# 1, 2, 4, 8, 16, 32, … 
def getModulo(n, d):
  
     return ( n & (d - 1 ) )
           
# Driver program to
# test above function 
n = 6
  
#d must be a power of 2
d = 4 
print (n, "moduo" , d, "is" , getModulo(n, d))
  
# This code is contributed by 
# Smitha Dinesh Semwal

C#

// C# code for Compute modulus
// division by a power-of-2-number
using System;
  
class GFG {
      
// This function will return n % d.
// d must be one of: 1, 2, 4, 8, 16, 32, … 
static uint getModulo( uint n, uint d)
{
return ( n & (d-1) );
}     
  
// Driver code
static public void Main () 
    {
     uint n = 6;
     uint d = 4; /*d must be a power of 2*/
  
     Console.WriteLine( n + " moduo " + d + 
                 " is " + getModulo(n, d));
      
     }
}
// This code is contributed by vt_m.

的PHP

<?php
// This function will return n % d.
// d must be one of: 1, 2, 4, 8, 16, 32, … 
function getModulo( $n , $d )
{
return ( $n & ( $d - 1) );
}     
  
// Driver Code
$n = 6;
  
// d must be a power of 2
$d = 4; 
echo $n , " moduo" , " " , $d , " is " , " " , getModulo( $n , $d );
      
// This code is contributed by vt_m.
?>

参考文献：

http://graphics.stanford.edu/~seander/bithacks.html#ModulusDivisionEasy

如果你在上述程序/算法或其他解决相同问题的方法中发现任何错误, 请发表评论。