Thread: Power of N + Overcome Size Limitations

I'm bored here's a decimal power-of-2 using simple carry-add. Don't expect your grader to believe you wrote it yourself though.

Code:

#include <iostream>
int main(){
	int p=10,*d=new int[p],s=1,b,i,j,c,*t;*d=1;
	std::cout<<"Enter a number: ";
	std::cin>>b;
	for(i=0;c=0,i<b;++i){
		for(j=0;j<s;++j){
			j[d]+=j[d]+c;
			c=j[d]>9?1:0;
			j[d]-=j[d]>9?10:0;
		}
		if(c){
			d[s++]=c;
			if(s==p){
				t=new int[p<<=1];
				for(j=0;j<s;++j)j[t]=j[d];
				delete[]d,d=t;
			}
		}
	}
	std::cout<<"2^"<<b<<"\n";
	for(i=s-1;i+1;--i)std::cout<<i[d];
	return 0;
}

It can do 2^100000 in 15~20 seconds. I could use binary splitting and Karatsuba/FFT, but hey this is a forum post. Perhaps you'll understand it someday.

Anyway, there is a shortcut. The << operator isn't only for cout. On integers, it shifts bits. (It's called the left shift operator.) Imagine that the number 19 is written in binary: 10011. What the left shift does is, it shifts all the bits left and adds a zero in the empty slot. So you get 100110 for (19 << 1), 1001100 for (19 << 2) and so on. So (2^X) == (1 << X). Have fun.

Code:

total = 1  << (power);

But, lets' back-up a bit...

...a program that asks the person for a number and then will out put that number by the power of 2...

The above means square the number (i.e. 6^2 = 6*6 = 36), which does not requre a loop, and is different from:

...so 2 ^ 6 = 64.

Which I assume is the correct assignment (i.e. 2^6 = 2*2*2*2*2*2) = 64

I doubt this assignment is about bit-shifting. I'll bet you are studying loops. If you use bit shifting you are not going to get credit, and you are not going to learn about loops. And, if they give you a "power-of-3" problem on a test, you are not going to be able to solve it! (The bit shifting "trick" only works with powers of two.)


First, get it working without a loop...*

Code:

power = 0;  // Initialize outside loop. (Don't need this 'till a loop is used.)
result = 1; // X^0 always equals one
cout<< "2^0 = " << result ;

power++;  // Needed later to keep track of the number of loops
result = result * 2; // 1*2 = 2, 2^1 = 2
cout<< "2^1 = " << result  << endl;  

power++;
result = result * 2; // 2*2 = 4, 2^2 = 4
cout<< "2^2 = " << result << endl; 

power++;
result = result * 2; // 4*2 = 8, 2^3 = 8
cout<< "2^3 = " << result << endl;

power++;
result = result * 2; // 8*2 = 16, 2^4 = 16
cout<< "2^4 = " << result << endl;

* That's always a good approach. Don't try to write the whole program at once. Write a few lines of code. Test-compile & test-run. Then add a few lines at a time test-compiling and test-running as you go.