Я хочу получить бит переноса добавления двух 64-битных целых чисел без знака в c. Я могу использовать x86-64 asm, если это необходимо. код:
#include <stdio.h>
typedef unsigned long long llu;
int main(void){
llu a = -1, b = -1;
int carry = /*carry of a+b*/;
llu res = a+b;
printf("a+b = %llu (because addition overflowed), carry bit = %d\n", res, carry);
return 0;
}
Как @EugeneSh. наблюдает, перенос равен либо 0, либо 1. Более того, учитывая, что a и b имеют один и тот же тип unsigned, их сумма корректно определена, даже если арифметический результат превышает диапазон их типа. Кроме того, (C) результат суммы будет меньше, чем a, и b, когда происходит переполнение, и больше, в противном случае, поэтому мы можем использовать тот факт, что реляционные операции C оцениваются либо как 0, либо как 1, чтобы выразить бит переноса как
carry = (a + b) < a;
Это не требует никаких заголовков и не зависит от конкретной верхней границы или даже от того, что a и b имеют один и тот же тип. Пока оба имеют типы без знака, он правильно сообщает о том, переполняется ли сумма более широким из их типов или unsigned int (в зависимости от того, что шире), что совпадает с их суммой, устанавливающей бит переноса. В качестве бонуса это выражается в виде самой суммы, что, я думаю, дает понять, что тестируется.
carry_out = (a + b + carry_in) < a не работает, потому что, например, b = 0xFFFF... и carry_in = 1 уже произвели перенос, который вы не обнаружите, если a + 0 < a равно false. Но да, для добавления с выносом, но не с переносом, это прекрасно работает. А современные компиляторы часто могут оптимизировать c+d + carry в инструкцию adc. Вы только столкнетесь с большими проблемами, заставляя компиляторы генерировать цепочку add/adc/adc/adc, где вам нужно использовать перенос из adc, а не add.
- person Peter Cordes; 07.05.2019
unsigned. (a + b) < a недостаточно для unsigned char
- person chux - Reinstate Monica; 08.05.2019
Перенести можно только 0 или 1. 1 если был перенос и 0 в противном случае. Обращение происходит в случае, если a + b > ULONG_LONG_MAX истинно. Обратите внимание, это в математических терминах, а не в терминах C, так как если a + b на самом деле переполняется, то это не сработает. Вместо этого вы хотите изменить его на a > ULONG_LONG_MAX - b. Таким образом, значение переноса будет:
carry = a > ULONG_LONG_MAX - b ? 1 : 0;
или любой эквивалент предпочтительного стиля.
limits.h.? 1 : 0 лишнее.
- person jxh; 07.05.2019
if/else. Вы можете выбрать один.
- person Eugene Sh.; 07.05.2019
carry = __builtin_add_overflow(a, b, &res)сохраняет младшие биты результата вresи устанавливаетcarry, если произошло переполнение. (На самом деле функция возвращаетbool, то естьtrueилиfalse, поэтому присвоение ееcarryдаст 1 или 0.) - person Eric Postpischil schedule 07.05.2019-1беззнаковому целому числу? Это Undefined Behavior, и вы можете получить от этого что угодно, даже сбой программы. - person Luis Colorado schedule 09.05.2019