Пользовательское обнаружение переполнения

Я работаю с тессеральной арифметикой, и мне нужно обнаружить переносы в определенных областях слова. Из-за характера программы расположение битов зависит от ввода. Например, с 32-битным размером слова и, скажем, входными данными 6 бит, мне было бы интересно проверить биты 19 и 3 для переноса сложения и биты 31 и 15 для вычитания (в более общем плане интересными битами являются (размер слова - 1), (размер слова / 2 + входные биты / 2), (размер слова / 2 - 1) и (входные биты / 2)).

То, что я думаю, это что-то вроде строк:

  (after addition)         ((NumberToCheck & (1 << 19 + 1 << 3)) != 0)  --> carried bit(s)

  (or after subtraction)   ((NumberToCheck & (1 << 31 + 1 << 15)) != 0) --> carried bit(s)

Есть ли лучший подход к этому?


algorithm math bit-manipulation integer-overflow
person bendicott    schedule 29.02.2012    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Вы можете найти все переносы из целых чисел a, b и их суммы s, вычислив carry-ins = a XOR b XOR s.

Естественно, переносы также являются переносами из непосредственно предшествующих битовых позиций.

Самый значительный перенос (указывающий на беззнаковое переполнение) может быть определен, говоря языком C/C++, с помощью most-significant-carry-out = (a > 0xFF...FF - b), где 0xFF...FF — соответствующее максимальное значение, а a и b — неотрицательные значения.

Вычитание можно свести к сложению. См. мои ответы на этот вопрос и этот вопрос.

person Alexey Frunze    schedule 01.03.2012
comment
Я не уверен, что этот подход сделает то, что мне нужно; поскольку я работаю с тессеральной арифметикой, я сначала раскладываю биты в слове, над которым работаю. Затем мне нужно проверить наличие переносов сразу в двух местах; один для координаты x и один для y. В приведенном выше примере у меня было бы что-то вроде 00000xxx00000xxxb (где каждый x представляет собой какое-то значимое значение, а каждый 0 — нет), поэтому присвоение максимального числа поможет только с левым подсловом. - person bendicott; 02.03.2012
comment
Если это поможет, меня также интересует только положительное пространство, поэтому a и b всегда будут положительными значениями. Каждое подслово всегда будет увеличиваться или уменьшаться только на единицу, что еще больше упрощает ситуацию — я знаю, где будут происходить переносы, если они есть. Меня больше всего интересует скорость; есть ли лучший способ проверить изменения этих конкретных битов? (Извините за двойное сообщение, в один комментарий не влезет) - person bendicott; 02.03.2012