+136
- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
#include <stdio.h>
#include <inttypes.h>
inline uint8_t mid_ch (uint8_t a, uint8_t b, uint8_t res)
{
if (b == 0){ if (a >= 2) return mid_ch (a-2, b , res+1); else return res;}
if (a == 0){ if (b >= 2) return mid_ch (a , b-2, res+1); else return res;}
return mid_ch (a-1, b-1, res+1);
}
uint64_t mid_0_ch (uint64_t a, uint64_t b)
{
return mid_ch(a, b, 0);
}
int main(void)
{
printf("%u %u", mid_0_ch (253, 123), (253+123)/2);
return 0;
}
Нахождение среднего арифметического двух чисел через рекурсию. Сначала сделал для uint64_t чтобы это имело смысл, ведь сложение двух 64-битных чисел с записью результата в третье может привести к целочисленному переполнению (для 64-битных чисел, сложение которых может привести к переполнению, этот код работал чрезвычайно медленно, поэтому я ограничился 8-битными). При таком наркоманско-рекурсивном алгоритме этого переполнения не будет. 128-битные типы есть только как нестандартное расширение, но тогда еще возникает вопрос, как найди среднее арифметическое двух таких 128-битных чисел? А если есть 256-битные, то как тогда их них находить среднеарифметическое... ну и так далее.
Можно эту проблему еще решать через битовые маски т.е. убрать из обеих чисел самые старшие биты (предварительно сохранив их), сложить эти два числа, поделить на два, потом уже эти сохраненные биты вида 10000... или 0000... оба поделить на 2(сдвинуть на один разряд) и прибавить. Наркоманство какое-то.
Почему бы не сделать в С некий особый целочисленный тип, в котором любая фигня влезет, но который бы использовался только временно для промежуточных вычислений, чтобы не делать бэкапы битиков всяких?
Запостил: 
j123123,
31 Марта 2014
Follow us!
void average(uint64_t val_1[], uint64_t val_2[], uint64_t result[], len){
int bit_c=0;
int new_c;
// Считаем сумму
for(int i=0; i<len; i++){
result[i]=val_1[i]+val_2[i]+bit_c;
bit_c=bit_c?result[i]<=val_1[i]:result[i]<val_1[i];
}
// Сдвигаем на бит (делим на 2)
for(i=len; --i>=0;bit_c=new_c){
new_c=result[i]&1;
result[i]=bit_c?(result[i]>>1)|0x80000000L:(result[i]>>1)&~0x80000000L;
}
}
Никакой рекурсии, никакой побитовой обработки.
Потому что не все архитектуры умеют. А так было бы хорошо из Си контролировать флаги, да...
Хм, а в каких рахитектурах нет carry флага? И в каких рахитектурах результат умножения слов не представляет собой двойного слова... Имхо таких не существует... А если есть - то они неюзабельны чуть менее чем полностью.
NAME
div, ldiv, lldiv, imaxdiv - compute quotient and remainder of an integer division
SYNOPSIS
#include <stdlib.h>
div_t div(int numerator, int denominator);
ldiv_t ldiv(long numerator, long denominator);
lldiv_t lldiv(long long numerator, long long denominator);
The div() function computes the value numerator/denominator and returns the quotient and remainder in a structure named div_t that contains two integer members (in unspecified order) named quot and rem. The quotient is rounded toward zero. The result satisfies quot*denominator+rem = numerator.
А с делением оптимизатор и так неплохо разбирается. % и / с одинаковыми аргументами обычно сливаются в одно деление...
В стандартной библиотеке нет
Можно такое накостылить
Оптимизатор кстати любит заменять деление умножением если остаток не нужен и если деление нельзя свести к двоичным сдвигам каким-нибудь
Такие же наблюдения. Пробовал и в сишке, и в жаве. Задача та же число => строка.
Писал разные "оптимизации", типа замены деления умножением на константу, и вычисления модуля от константы всяким байтоебством.
Результат удивил /,% - оказалось самым быстрым.
Короче всё идет по пути умных компиляторов/jitов, вся тяжесть и ответственность больше ложится на тех кто пишет эти вещи.
Проблема только в том, что беззнакового MUL'а нет. Это и имелось в виду?
Емнип надо прибавить знаки исходных операндов к результату.
mov eсx, eax #a - eax
imul ebx #b - ebx
sar ecx,31
sar ebx,31
add ebx,ecx
add eax,ebx
adc edx,0
Дело в том что так уже повелось с тех времен, и если что и добавят то только встроенными в компилер функциями, как и сказано ниже.
В мане рекомендуют его юзать так:Для двух слов это вполне канает. Только вот carry флаг после третьей строки может быть кривым. Например, если мы складываем FFFF и FFFF, то получим FE в r3 и взведенный carry, затем r2 прокрутится на 0, а затем мы получим в r4 00+FF=FF. Но carry уже не будет. Как же это юзали для длинной арифметики? :)
Ну не напрямую, конечно. Например сделать intrinsic функцию для сложения, которая принимает bool (входящий перенос) и два числа, и возвращает ответ и bool (перенос в следующий разряд). А оптимизатор уже преобразует эту штуку в использование carry флага и add/adc. Ну либо не преобразует, если в коде намутили что-то слишком ужасное.
Ну многие инструкции уже запилили именно так. Однако слышал мнение что intrinsicи - зло.