0001 __int64 power ( __int64 a, int n ) { //a^n㷨n >= 0 0002 __int64 pow = 1; //O(1) 0003 __int64 p = a; //O(1) 0004 while ( 0 < n ) { //O(logn) 0005 if ( n & 1 ) //O(1) 0006 pow *= p; //O(1) 0007 n >>= 1; //O(1) 0008 p *= p; //O(1) 0009 } 0010 return pow; //O(1) 0011 } //power()