Clash Royale CLAN TAG#URR8PPP

How to find antilog(base 2) of a number?

I used a for loop to find antilog of the given number.

int g = 0, m, diff = 10;
for(j = 0; g <= diff; j++)

g = pow(2, j);

m = j - 2;
cout << m;


It gives the power of 2 for which g is the number just less than diff.

g

diff

I tried the base change theorem of log to find the antilog of the number something like this:

m = log(diff) / log(2);


without the for loop, but in this case whenever there is a number that is an exact multiple of 2s for example 8, then it gives 2 as the answer and not 3.

And using for loop for doing so is in a program is exceeding the time limit.

Is there a shorter and reliable way to do so?

cout << m;

int

pow(2, j)

1 << j

2 Answers
2

Here is a fun solution without looping:

function antilog(int input) = pow2 >> 16; // turn on all bits < MSB
pow2


The latter half of which was adapted from some part of the bit twiddling hacks. (Knowing the source, there is probably some other function faster than this doing what you've asked.

Solutions aside, it should be noted that what particularly is causing your solution to be slow is the repeated calls to pow, which is a relatively expensive function. Because you are doing integer arithmetic (and what's more, multiplying by 2, every computer's favorite number), it is much more efficient to write your loop as the following:

pow

2

int g=1,m,diff=10;
for(j = 0; g <= diff && g <<= 1; j++) /* empty */;
m=j-2;
cout<<m;


Which is quite the hack. int g=1 initializes g to the value it takes on the first time the code executes the body of the loop you've written. The loop conditions g <= diff && g <<= 1 evaluates to g <= diff. (Notice that this is a problem if diff >= 1 << (8 * sizeof(int) - 2), the greatest power of two we can store in an int). The empty statement simply allows us to have a well-formed for statement the compiler (mostly) won't complain about.

int g=1

g <= diff && g <<= 1

g <= diff

diff >= 1 << (8 * sizeof(int) - 2)

Use integer arithmetic and build up the power incrementally. For example:

#include <iostream>

using namespace std;

int main()

for (int diff = 1; diff < 129; diff += 5)

int p = 1;
int j;
for (j = 0; p <= diff; j++)

p *= 2;

cout << diff << " = " << (j - 1) << 'n';




Sample output:

1 = 0
6 = 2
11 = 3
16 = 4
21 = 4
26 = 4
31 = 4
36 = 5
41 = 5
46 = 5
51 = 5
56 = 5
61 = 5
66 = 6
71 = 6
76 = 6
81 = 6
86 = 6
91 = 6
96 = 6
101 = 6
106 = 6
111 = 6
116 = 6
121 = 6
126 = 6


An alternative test strategy tests boundaries:

#include <iostream>

using namespace std;

int main()

int diff = 1, 2, 3, 4, 5, 7, 8, 9, 15, 16, 17, 31, 32, 33, 63, 64, 65 ;
int size = sizeof(diff) / sizeof(diff[0]);
for (int i = 0; i < size; i++)

int p = 1;
int j;
for (j = 0; p <= diff[i]; j++)

p *= 2;

cout << diff[i] << " = " << (j - 1) << 'n';




Sample output:

1 = 0
2 = 1
3 = 1
4 = 2
5 = 2
7 = 2
8 = 3
9 = 3
15 = 3
16 = 4
17 = 4
31 = 4
32 = 5
33 = 5
63 = 5
64 = 6
65 = 6


Clearly, the inside of the test loop should be wrapped into an antilog₂ function — except for the printing operation.

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.