知道掩码求掩码长度

Problem statement: We have given two numbers "a" and "b". Now compute the value of "a" raise to the power "b" i.e. (a^b) by using bitmasks.

问题陈述：我们给了两个数字“ a”和“ b” 。 现在， 通过使用位掩码计算将“ a”的值提高到幂“ b”，即(a ^ b) 。

Example:

例：

Input:    a = 3 , b = 5    Output:    a^b = 243

Algorithm:

算法：

This method uses bitmasks and without using extra space to calculate a^b in O(log b) time.

此方法使用位掩码，并且不使用额外的空间来计算O(log b)时间中的a ^ b 。

1. Let's take variable ans in which we store the result and initialize it with 1.

   让我们使用变量ans来存储结果，并使用1对其进行初始化。

2. Extract last bit from b.

   从b中提取最后一位。

3. If the Extracted bit is 1 multiply ans with a, otherwise if the Extracted bit is 0 then don't multiply.

   如果Extracted位为1 ，则将an与a相乘；否则，如果Extracted位为0，则不要相乘。

4. Update a to a*a.

   更新 到*一个 。

5. Discard rightmost bit i.e right shift b by 1.

   丢弃最右边的位，即右移b 1 。

6. Repeat steps 2 to 5 until b becomes 0.

   重复步骤2到5，直到b变为0为止。

ans = 1    while(b>0)    {        if(b&1){            ans = (ans * a);        }        a = a*a;        b = b>>1;    }    //Now ans contains the value of a^b.

Explanation with example:

举例说明：

C ++程序使用位掩码实现快速幂运算 (C++ program to implement Fast Exponentiation using Bitmasking)

#include
    
     using namespace std;long long calculate(int a,int b){
   	// initialize ans with 1	long long ans = 1;	while(b>0)	{
   	// check if last bit 1		  if(b&1){
   	     ans = (ans * a);	  }	  	// update value of a by a*a  	  a = a*a;	  	// right shift b by 1  	  b = b>>1;	}		return ans;}int main(){
   	int a,b;	long long ans;	cout<<"enter the value of a and b : ";	cin>>a>>b;		cout<<"a^b = "<
     
      <
      
       <
      
     
    

Output

输出量

First run:enter the value of a and b : 5 3a^b = 125Second run:enter the value of a and b : 37 7a^b = 94931877133Third run:enter the value of a and b : 37 0a^b = 1

翻译自:

知道掩码求掩码长度