In this article, we will learn fast exponentiation using bit masking. Exponentiation is used in many real-world applications including scientific research. The traditional method of way too slow to consider for real-life applications. Hence in this article, we’ll make use of bit masking concepts to derive a more optimized technique.

Be it your mathematics homework problem or the calculation of complex reaction kinematics in a nuclear reactor, who doesn’t want to do it fast?

Exponentiation Naive Approach

In the traditional approach, we simply keep on multiplying the base value with itself until the power matches the required power. However, this method is insufficient because for exponentiation up to larger values say 50 or 60, we will need to run a loop 50 or 60 times. Doing linear work for this simple task isn’t healthy for calculations. Let’s quickly jump to

What Is Bit Masking?

First things first, what bit masking actually is? The concept of bit masking proves to be magical as it can really trim the space and time complexities for certain problems. And exponentiation is one of those problems.

In this approach, we tend to represent states using bits(0 or 1). At a time a single bit can either be low or high. Hence, we can denote a total of 2N states in total using as few as N bits. We can also use this technique to optimize the time complexity of an algorithm.

Fast Exponentiation Using Bit Masking

Our aim is to compute the value of 'a' raised to the power 'n' in an efficient manner.

Approach

We can represent any number in its binary form, hence we can also represent the power ‘n’ in binary form. Let’s calculate the value of a5.

• We can represent 5 as: 22 x 1 + 21 x 0 + 20 x 1 = (101)2
• Now we aim to map the powers of 2 with each bit.
  • The first bit is mapped with 20, the second bit is mapped with 21, the third bit with 22 and so on.
• Once the bits are mapped, we with look at the set bits only.
• In this case the set bits are bit number 2 and 0 of 101.
  • Bit number 0 represents 20.
  • Bit number 2 represents 22.
• Now once the set bits are identified, we can simply represent the number as product of the powers of 2 mapped with these bits.
• In this case: a5 = a4 x a1
• We start by initializing the a temp variable with the value of ‘a’. And initialize the answer with 1.
• As we start traversing over the bits, we multiply the current value of the temporary variable by temp_variable. This step will take place for every bit under consideration.
• Start traversing over the bits.
  • If the current bit is 0 then do nothing, simply continue.
  • If the bit is a set bit(logic 1) then multiply the answer with current value of temporary variable.

Let’s calculate 35 using this method.

Code in C++

Output

Fast Exponentiation Output

Conclusion

Today we developed an algorithm for efficiently calculating the exponential values. Any number can be represented in binary form using log2N digits, and our algorithm iterates over these number of digits only. Hence we reduced the time complexity of exponentiation from O(N) to O(log2N). That’s it for today, thanks for reading.

Further Readings

If you want to explore bit masking further, then you can refer to the following websites.

https://www.hackerearth.com/practice/algorithms/dynamic-programming/bit-masking/tutorial/

https://www.learn-c.org/en/Bitmasks