CODEWITHSUNDEEP
binaryexponent
Steven
Steven

Reputation: 1809

Exponent Binary Numbers

Could someone tell me the logic behind exponenting binary numbers? For example, I want to take 110^10, but I don't know the logic behind it. If someone could supply me with that, it'd be a great help.. (And I want it to be done in pure binary with no conversions and no looping multiplication. Just logic...)

Upvotes: 1

Views: 13607

Answers (4)

Vogon Poet
Vogon Poet

Reputation: 101

Unfortunately the easiest way for your computer to handle simple exponents is your "looping multiplication" (or the naïve approach), which is the most rudimentary (and literal) way of handling it. As @user1561358 commented, it is NOT just binary adds and shifts. That is multiplication. To raise 66 (110110) the naïve approach has you multiplying the base n times (as below):

              110 
x             110
   --------------
           100100  =  36
x             110
   --------------
         11011000  =  216
x             110
   --------------
      10100010000  =  1296
x             110
   --------------
    1111001100000  =  7776
x             110
   --------------
01011011001000000  =  46656

The simple code for a naïve multiplication is elegant for most applications:

long long binpow(long long a, long long b) {
    if (b == 0)
        return 1;
    long long res = binpow(a, b / 2);
    if (b % 2)
        return res * res * a;
    else
        return res * res;
}

For larger or arbitrary exponents you can dramatically reduce the number of calculations by applying Horner's Method, explained in great detail in this video specifically calculating binary exponents.

In essence, you are just multiplying the bits with non-zero exponents. Let's look at 11021102, (or 66):

11021102 breaks down into the following exponents:

There is no "1" bit set so 61 won't be multiplied, but we do have the two and four bits to calculate:

6102 = 36

61002 = 1296

So, 66 = 36 x 1296 = 46656

The above code can be modified only slightly to check for non-zero exponents with a while {.. test:

long long binpow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

To really see the advantage of this let's try the binary exponentiation of

11121000000002, which is 7256.

The naïve approach would require us to make 256 multiplication iterations!

Instead, all the exponents except 2256 are zero, so they are skipped in the while loop. There is one single iterative calculation where a * a happens 256 times:

11121000000002 = (a 718 digit binary beginning with 11001101011....)

728 = 2213595400046048155450188615474945937162517050260073069916366390524704974007989996848003433837940380782794455262312607598867363425940560014856027866381946458951205837379116473663246733509680721264246243189632348313601

Upvotes: 0

cnd
cnd

Reputation: 1731

Binary exponents are very easy. They are simply additions and shifts only.

the number 110 is where you start. Working backwards from the number 10 - (i.e. 0) - it's a zero, so this means "do not add it in."

Now you shift left - so 110 becomes 1100

Now you work on the next bit of the 10 (i.e. 1) - it's a one, so this means "add this to the result" - it's 0 so far, because we didn't already add it, so the result is now 1100

there are no more bits to do - so the answer is 1100

If you were doing 110^110 - you would have one more to do - so - you again shift and get 11000 now.

The last bit is again a one, so now you add: 1100 + 11000 = 100100

110^10=1100 i.e. 6^2=12

110^110=100100 i.e. 6^6=36

Upvotes: 1

RustyTheBoyRobot
RustyTheBoyRobot

Reputation: 5955

peenut is correct in that exponentiation doesn't care what base you're representing your numbers in, and I don't know what you mean by "just logic," but here's a stab at it.

A quick search over at Wikipedia reveals this algorithm. The basic ideas is to square your base, store the result, and then square the result and repeat. This will give you the factors of your answer, which you can then multiply together. I think of it as a "binary search"-flavored exponentiation algorithm since you can skip a lot of intermediate steps by squaring and storing.

Upvotes: 1

peenut
peenut

Reputation: 3426

Exponentiation is operation that is independent of actual textual representation of number (e.g. in base 2 - binary, base 10 - decimal).

Maybe you want to ask about binary XOR (eXclusive OR) operation?

Upvotes: 0

Related Questions