Что случилось с моей реализацией функции питания?

Question

Я написал код для простой проблемы в leetcode. Он просит реализовать pow (x, n); Он говорит мне, что «ошибка времени выполнения», последний выполненный вход: 1.00000, -2147483648. Я перешел на другой метод, который работает. Но я просто хочу знать, что я делаю неправильно в следующем коде. Огромное спасибо!!

class Solution { 
public: 
    double pow(double x, int n) { 
     // IMPORTANT: Please reset any member data you declared, as 
     // the same Solution instance will be reused for each test case. 
     if(n==0 && x==0) return 1.0; 
     if(x==0) return 0; 
     if(n==0) return 1.0; 
     if(n<0) return 1/pow(x,-n); 
     if(n==1) return x; 

     double y=pow(x,n/2); 
     if(n%2==1) return y*y*x; 
     else return y*y; 

} 

};

Answer 1

Предполагая, что int имеет длину 32 бита, -2147483648 - единственное уникальное значение, отличное от 0, в котором его отрицание равно самому себе. Таким образом, линия:

if(n<0) return 1/pow(x,-n); 

вызывает себя с теми же параметрами и делает это до тех пор, пока не произойдет переполнение стека.

Более подробно, двоичное представление -2147483648 является:

10000000000000000000000000000000 

Это 1 следуют 31 0 с. Взятие отрицания в соответствии с two's complement является двухэтапным процессом. 1) Измените все 0 с до 1 и наоборот:

01111111111111111111111111111111 

затем 2) добавить 1:

10000000000000000000000000000000 

Таким образом, мы получаем обратно то же значение. Отсюда бесконечная рекурсия.

Если вы ДОЛЖНЫ обрабатывать этот случай, вот одна идея. Вставьте этот раз перед испытанием n<0:

if (n==-2147483648) return 1/(x*pow(x,2147483647)); 

Очевидно, что это хак для этого одного случая. В конечном итоге ваша проблемная область определит самое элегантное/общее решение.

Answer 2

-2147483648 is hex 80000000 - наибольшее отрицательное число, и один больше, чем наибольший положительный. Поэтому, когда n = -2147483648, нет -n. Код не будет завершен на линии

if(n<0) return 1/pow(x,-n); 

Это, конечно, особый случай.