C++ Help?!

[MAME]

I have an assignment to take a number from the user, and then see what the smallest power of two that starts with the same number.
For example: if you entered 51, the first power of 2 would be 9 (2^9 = 512).

So I'm trying to do it in C++, but I don't know how to compare the user input to each power of 2 that is outputted. In other words, lets say you entered 51, how do I look at only the first 2 digits of the output of my power of two function to see if they're equal to 51?

I already came up with a way of doing it but I know it cannot be the most efficient way.
I divide the user input by 10 until it's equal to 0 (integer division) to find the number of digits in the input number (lets call it numOfPlaces). Then I do the same divide by 10 for each output of the power of two to find it's length (lets call it powOfTwoPlaces). Then again, I divide the power of two by 10 powOfTwoPlaces - numOfPlaces times. Then I compare the original input with the remaining numOfPlaces length power of two.

It's just so terribly ineffecient...I'd really like to skip all that busy work for each power of two!

 

[gwlam12]

why dont u just make a loop out of ur algorithm

 

[MAME]

it does loop to find those values and loops again to compare...but it's still very very horrible and ugly.

Also, does anyone know which data type is the largest in terms of size (for numbers). Long int? I can include any package I need.

 

[superhuang]

A long long is 64 bits on typical platforms.

Great technical interview question.

Forget the math. Digit-by-digit compares are difficult and costly (division takes way too long) on a machine that doesn't understand numbers in base-10 form. Especially when comparing starting at the MSB. Just reinterpret the numbers in string form (sprintf or c++ streams), and do a character-by-character comparison (strncmp through strlen of input) that way. Roughly:



for (int i=0; ; i++) {
power = 1 << i;
sprintf(buf1, "%d", power);
sprintf(buf2, "%d", input);
if (strncmp(buf1, buf2, strlen(buf2)) == 0)
return power;
}

Of course, this c snippet ignores boundary conditions on the input and also never terminates. But that's the general idea.

 

[MAME]

Ah, I've never used C but I have to convert a small insertion sort program I wrote in to C tomorrow. I don't understand your code snipbit 100% but I was thinking about using strings.

Is there anything longer than a long long?

I know it's costly but I was told not to worry about efficency. Here's my end result:
#include <iostream>
#include <math.h>

using namespace std; //introduces namespace std
int main( void )
{
long int input, inputTemp, powOfTwo, powTemp;
int decPlaces = 0, powPlaces = 0, i = 0;
bool flag1 = true, flag2 = true, flag3 = true;

cout << "Enter a number and I'll return the first power of two that" <<
" starts with the same number: ";
cin >> input;
inputTemp = input;

//find number of decimal places in user's input
while(flag1)
{
inputTemp = inputTemp/10;
if(inputTemp == 0)
flag1 = false;
decPlaces++;
}

while(flag3)
{
powOfTwo = pow(2, i);
powTemp = powOfTwo;
powPlaces = 0;
while(flag2) //find number of decimal places in each power of two
{
powTemp = powTemp/10;
if(powTemp == 0)
flag2 = false;
powPlaces++;
}
flag2 = true;

if(powPlaces > 1 && powPlaces > decPlaces)
for(int j = 0; j<(powPlaces - decPlaces); j++)
{
powOfTwo = powOfTwo/10;
}
//check if the power of two starts with the user input
if(input == powOfTwo)
{
cout << "\n2 to the "<<i<<"th power = " << pow(2,i) << ", which starts with " << input;
flag3 = false;
}
i++;
}

return 0;
}


god damn, the spacing looks fine when I preview, but is crap when I post.

 

[MAME]

He asked us to try it with an input of 97. This doesn't work on my program, even with a long long. It might be ok if I used a long double, but i need to do integer division (round down every time). I guess I'll go look up the function for the floor of a number...it's in math.h right?


Ok, nevermind. I used a long double and it was fine, except the damn presision was adding a .000000000000000001 which messed up my comparrison. So I just floored it right before I compared.


Damn, my version was messy as hell...should have used strings!