Как следить за знаком переменной при переполнении в C++?

Question

[dmasloff]

Есть задача, где нужно следить за знаком переменной в long long в результате переполнения. Суть в том, что нам даётся натуральное число (оно меньше 10^9), и на каждом шаге мы умножаем число, хранящееся в long long (сначала это 1) на данное натуральное число и нам нужно найти на каком шаге переменная станет отрицательной. Попытался реализовать это через логарифм по основанию 2 (ceil(63.0/log2(x))), но так можно считать только количество шагов до переполнения типа, а для некоторых значений переменной при переполнении мы попадаем опять в положительные числа. Попытался реализовать рекурсивную функцию, но и она не работает. Соответственно, как наиболее удобно следить за этим, не используя прямое умножение внутри while?

#include <iostream>
#include <cmath>

using namespace std;

int f(long long a, int temp) {
	if (a == temp) {
		int ft = ceil(63.0 / log2(temp));
		if ((long long)pow(temp, ft) <= 0) {
			return ft + 1;
		}
		else {
			return ft + f(pow(temp, ft), temp);
		}
	}
	else {
		int ft = ceil((63.0 - log2(a)) / log2(temp));
		if ((long long)a * pow(temp, ft) <= 0) {
			return ft + 1;
		}
		else {
			return ft + f(a * pow(temp, ft), temp);
		}
	}
}

int main() {
	long long a, temp;
	cin >> a;
	temp = a;
	cout << f(a, temp);
}

Comments

[Евгений Шатунов]

dmasloff , если в результате операции со знаковым типом происходит переполнение разрядов, дальнейшее поведение программы не определено.
У тебя код полностью не верен. Как вариант правильного кода, ты можешь использовать операцию над беззнаковыми целыми, переполнение которых определено и ведет к отбрасыванию данных вне диапазона бит используемого целого типа.

Answer 1

[xorknown]

У вас неправильный подход. Если взять абстрактную машину, то нельзя следить за знаком переменной, так как стандарт не гарантирует, что он изменится. Вам вообще по факту переполнять нельзя.
Вам надо определить это до самого переполнения. Самый тупой способ - вычесть из максимального числа один из аргументов и сравнить полученное число со вторым аргументом(если полученное число меньше, то значит переполнение).