Получение модуля числа без операции сравнения

#алгоритм #c #cpp

Берем простой код:
void main() {
    int x = abs(-1);
}

Собираем и дизассемблируем его:
$ gcc sample.c -o sample && objdump -d ./sample

Получаем листинг, где нет условной команды:
80483a1:    e8 ee ff ff ff          call   8048394 
80483a6:    89 c2                   mov    %eax,%edx
80483a8:    c1 fa 1f                sar    $0x1f,%edx
80483ab:    31 d0                   xor    %edx,%eax
80483ad:    29 d0                   sub    %edx,%eax

Как на C/C++ получить абсолютное значение целого числа без операции сравнения?    

Ответы

Ответ 1

ассемблерная операция sar это обычный сдвиг вправо.
Вот ваш код:
int myabs(int x)
{
    //mov    %eax,%edx
    //sar    $0x1f,%edx
    int minus_flag = x>>0x1F;//0x1F = 31

    //xor    %edx,%eax
    int y =  minus_flag ^ x;

    //sub    %edx,%eax
    y -=minus_flag;
    return y;
}


Ответ 2

Я лучше ориентируюсь в Java, поэтому чтобы не выглядить глупо код не буду писать на C :)
Но с алгоритмической точки зрения это должно выглядеть примерно так:
(Я полагаю, на С/С++ представление знакового целого сделано с помощью дополнительного
кода)

Скопировать куда-нибудь первый бит.
Создать новую целую переменную такого же размера.
Скопировать во все биты второго числа значение сохранённого ранее бита.
Применить побитовое "исключающее или" первого числа ко второму (XOR).
Прибавить к получившемуся числу значение сохранённого ранее бита.

Приведу таблицу действий для чисел -5 и 3 которые хранятся в 8 битах.
число1 доп.число1 доп.бит1 число2 доп.число2 доп.бит2 

11111011 00000000 1 00000011 00000000 0
11111011 00000000 1 00000011 00000000 0
11111011 11111111 1 00000011 00000000 0
00000100 11111111 1 00000011 00000000 0
00000101 11111111 1 00000011 00000000 0

Алгоритм не супер, но он без сравнений :)


Ответ 3

Первое, что пришло на ум, сразу после прочтения вопроса, - это взять квадратный корень
из квадрата числа:
sqrt(x*x)

Другой вариант - это, как уже здесь отмечалось, воспользоваться знаниями о представлении
числа и дополнительном коде и побитовыми операциями.
Пример для 8-битных чисел
char x = -5;
char minus = (x & 0x80) >> 7;            // равно 1 если x - отрицательное и 0 если
положительное
char plus = (((x & 0x80) >> 7) + 1) & 1; // наоборот, равно 1, если x - положительное,
и 0 если отрицательное
char abs_x = minus * (-x) + plus * x;

Для int будет сложнее, т.к. нужно будет учитывать кучу особенностей, например, разрядность
(int может быть 8, 16, 32, 64-разрядной) и порядок байтов (Little-Endian/Big-Endian).


Ответ 4

Алгоритмический трюк, на котором основано вычисление модуля без ветвлений, заключается
в свойстве дополнительного кода. Операция xor с числом -1 даёт инвертирование битов
числа, а прибавление 1 завершает переход к отрицанию числа. Причем само число -1 получается
как знаковый сдвиг вправо исходного числа, если оно было отрицательным. Если же число
было положительным, что сдвиг даст 0, поэтому xor и sub ничего не изменят. Подробнее
о подобных алгоритмах вычисления модуля и о скорости их работы можно прочитать здесь.