c - Умножение фракций с побитовыми операциями

Question

Итак, я застрял, пытаясь выяснить, как умножить дробь (3/4) на целое число со знаком в c. Задача заключается в использовании только логических операторов (! ~ &^| + < < >>) без инструкций (if, циклов и т. Д.) И с использованием максимально 12 логических операторов. Цель состоит в том, чтобы точно выразить следующее выражение (x * 3/4). Теперь я рассмотрел другие вопросы с аналогичной проблемой (только с разной долей), однако в решениях для них используется более 12 операторов. Я пробовал упростить их, но просто не могу сделать этого, не имея решения, которое не работает. Вот решение от 5/8 вопроса:

int s = -((num >> 31) & 1); // sign bit as -1 or 0 

int n = (num^s) - s; // twos complement if negative 

int x = n >> 3; // divide by 8 

x = (x << 2) + x; // multiply by 5; no overflow yet since 5/8 is less than one 

int y = n & 7; // the bits we shifted out 

y = (y << 2) + y; // multiply by 5; no overflow 

return (s^(x + (y >> 3))) - s; // the two pieces and complemented back 

Я не уверен, если выше метод является правильным, так как я подключен -2 и сделал это от руки и получил -3 обратно. Должно было быть -1 с -2 * (5/8) = -1.25

Мое первоначальное мышление, чтобы решить это, было проверить и переполнить. Это связано с тем, что простая программа, например:

x = (x<<1) + x; 
x = X>>2; 

В случае переполнения ответ будет отключен на +1. Чтобы решить проблему, я подумал, что мне нужно будет разделить пределы на 3 и проверить и посмотреть, будет ли умноженное целое число больше 715827882 или -715827882. Если число больше, получите 1 из сравнения и добавьте его в конечный результат или если он меньше, чем затем, получите 0 и добавьте 0 к окончательному результату. Я чувствую, что этот способ трудно реализовать без инструкций if, и что он может использовать более 12 операторов. Я просто прошу о помощи в том, что может быть лучшим способом подойти к проблеме. Заранее спасибо!

Answer 1

Что вы думали только о том:

x=(x<<1)+x; // do x=x*3 x=x>>2; // do x=x/4

Это может переполниться, так как x удерживать большее значение первого. Будет ли это работать?

x=x-(x>>2); // do x=x-x/4, equal to 3/4

Конечно, потому что x>>2 выбрасывает младший бит, поэтому результат округляется до. Если вам нужно усечения вниз, это неправильно, и вы должны использовать дополнение:

x=(x>>1)+((x+1)>>2); // x=x/2+x/4

EDIT: вам нужно (x+1)>>2, чтобы избежать двойного результата усечения теряется, например, х = 7.