Переполнение 32-битной переменной

Question

В настоящее время я реализую уравнение (2^A)[X + Y*(2^B)] в одном из моих приложений.

Проблема связана с переполнением 32-битного значения, и я не могу использовать 64-битный тип данных.

Предположим, когда B = 3 и Y = 805306367, он переполняет 32-битное значение, но когда X = -2147483648, результат возвращается к 32-битному диапазону.
Поэтому я хочу сохранить результат (Y*2^B). Может кто-нибудь предложить какое-то решение для этого .... A и B имеют значения от -15 до 15, а X, Y могут иметь значения от 2147483647..-2147483648.
Выход может варьироваться от 0...4294967295.

Answer 1

Если число слишком велико для 32-битной переменной, то вы либо используете больше битов (либо путем сохранения в большей переменной, либо с использованием нескольких переменных), либо вы отказываетесь от точности и сохраняете ее в плавающей запятой.Поскольку Y может быть MAX_INT, по определению вы не можете умножить его на число, большее 1, и все равно поместить его в 32-разрядное целое число.

Answer 2

Если вы не можете использовать 64-битную версию, потому что ваш локальный C не поддерживает их, а не по какой-либо другой первостепенной причине, вы можете рассмотреть Многофункциональная арифметическая библиотека GNU при http://gmplib.org/

Answer 3

Исходя из значений для A и B в назначении, я предполагаю, что ожидаемое решение будет включать это:

• следующее лучше всего делать без знака, поэтому сохраняйте знаки X и Y и оперируйте их абсолютным значением

• Храните X и Y в двух переменных, каждая из которых содержит старшие 16 бит, а другая - младшие что-то вроде
  int hiY = Y & 0xFFFF0000;

  int loY = Y & 0x0000FFFF;

• Сдвиньте старшие части вправо, чтобы у всех переменных были старшие биты 0

• Y * (2 ^ B) - это смещение Y влево на B бит. Это эквивалентно смещению старшей и младшей частей на B битов, и, поскольку вы сместили старшую часть, обе операции поместятся в их 32-битное целое число

• Процесс X аналогичным образом в верхней и нижней частях

• Отслеживание знаков X и Y вычисляет X + Y * (2 ^ B) для верхних и нижних частей

• Снова сдвиньте как верхний, так и нижний результаты на биты A

• Соедините верхнюю и нижнюю части в окончательный результат

Answer 4

В этом случае я бы использовал цикл вместо умножения.Примерно так:

int newX = X;
int poweredB = ( 1 << B ); // 2^B
for( int i = 0; i < poweredB ; ++i )
{
    newX += Y; // or change X directly, if you will not need it later.
}
int result = ( 1 << A ) * newX;

Но note : это будет работать только для некоторых ситуаций - только еслиу вас есть гарантия , что этот результат не будет переполнен.В вашем случае, когда Y - большое положительное число, а X - большое отрицательное число («большое» - ага, это слишком субъективно), это определенно сработает.Но если X большой положительный, а Y большой положительный - снова будет переполнение.И не только в этом случае, но и со многими другими.