Разделите целое число на 16, не используя деление или приведение

Question

Ладно ... позвольте мне перефразировать этот вопрос ...

Как я могу получить x 16-х целых чисел, не используя деление или приведение к удвоению ....

Answer 1

int res = (ref * frac) >> 4

(но немного беспокоиться о переполнении. Насколько велики могут быть ref и frac?

Answer 2

В любой операции такого рода имеет смысл сначала умножить, а затем разделить.Теперь, если ваши операнды являются целыми числами и вы используете компилируемый язык (например, C), используйте shr 4 вместо / 16 - это сэкономит некоторые циклы процессора.

Answer 3

Вы можете использовать сдвиг влево или вправо:

public static final long divisionUsingMultiplication(int a, int b) {
    int temp = b;
    int counter = 0;
    while (temp <= a) {
        temp = temp<<1;
        counter++;
    }
    a -= b<<(counter-1);
    long result = (long)Math.pow(2, counter-1);
    if (b <= a) result += divisionUsingMultiplication(a,b);
    return result;
}

public static final long divisionUsingShift(int a, int b) {
    int absA = Math.abs(a);
    int absB = Math.abs(b);
    int x, y, counter;

    long result = 0L;
    while (absA >= absB) {
        x = absA >> 1;
        y = absB;
        counter = 1;
        while (x >= y) {
            y <<= 1;
            counter <<= 1;
        }
        absA -= y;
        result += counter;
    }
    return (a>0&&b>0 || a<0&&b<0)?result:-result;
}

Answer 4

Я не понимаю ограничения, но этот псевдокод округляется (?):

res = 0
ref= 10
frac = 2
denominator = 16
temp = frac * ref
while temp > 0
   temp -= denominator
   res += 1
repeat
echo res

Answer 5

Предполагая, что все здесь являются целочисленными значениями, любой оптимизирующий компилятор, достойный его внимания, заметит, что 16 - это степень двойки, и соответственно сдвигает дробь - при условии, что оптимизация включена Беспокоитесь больше об основных оптимизациях, которые компилятор не может сделать для вас.

Во всяком случае, вы должны заключить в скобки ref * frac и затем разделить, так как любое значение ГРП меньше 16 приведет к 0, будь то сдвиг или деление.