Как я могу разделить целое число со знаком, используя только двоичные операторы?

Question

Я могу только использовать! ~ & ^ | + << >>

Я пишу это на C.

Я пытаюсь разделить число х на 2^n. Поэтому я подумал, что если бы я сдвинул x >> n, это сработало бы, но оно не работает с нечетными отрицательными целыми числами. Изначально это выглядело так:

int dl18(int x, int n) {
   return (x >> n);
 }

но если x = -9 и n = 1, вывод должен быть -4, но это -5. и если x = -9 и n = 0, вывод верен (-9).

Заранее спасибо.

Итак, я понял, что благодаря этому все работает, если только n = 0 и x не отрицательное число:

return (~(x >> 31) & (x >> n)) | ((x >> 31) & ((x >> n) + 1));

Answer 1

Предполагая два дополнения представления целых чисел со знаком и поведение арифметического сдвига >> оператор, ответ может быть:

int dl18(int x, int n) {
    if (x < 0) {
        x += (1 << n) - 1;
    }
    return x >> n;
}

Дополнение необходимо, потому что >> округляет отрицательные числа к отрицательной бесконечности. Добавляя 2^n - 1результат всегда обрезается до нуля, как это происходит для / оператор.

Из-за ваших требований, предполагая, что int имеет 4 байты (и быть лишним педантичным CHAR_BIT = 8), выражение может быть переписано (обфусцировано) как:

(x + ((x >> 31) & ((1 << n) + ~0))) >> n

Идея x >> 31 должен дублировать бит MSB, поэтому маска становится одной из всех (т.е. 0xFFFFFFFF) или все нули, которые затем используются для сохранения или устранения ((1 << n) - 1) от сложения. Круглые скобки & необходимы, потому что сложение имеет более высокий приоритет, чем побитовое AND.

Этот алгоритм также используется компилятором GCC. Например:

int dl18_4(int x) { return x / 4; }

переводится с -O1 в:

dl18_4:
        lea     eax, [rdi+3]    ; eax = rdi + 3
        test    edi, edi        ; set sign flag if edi < 0
        cmovns  eax, edi        ; eax = edi if SF = 0
        sar     eax, 2          ; eax = eax >> 2
        ret

Обратите внимание, что смещение на отрицательное число вызывает неопределенное поведение, поэтому может быть безопаснее объявить второй параметр как unsigned int,

Answer 2

Вот решение, которое позволяет избежать смещения битов отрицательных значений. Он предполагает представление с двойным дополнением, но не использует унарный отрицательный оператор.

Битовая маска используется для установки neg к ненулевому значению, если x отрицателен или равен нулю, если x неотрицательный Здесь уловка, предложенная Grzegorz Szpetkowski, используется, чтобы избежать вычитания на 1: добавление ~0 вместо. Если x отрицательно, значение x изменяется на величину x, Чтобы избежать использования унарного отрицательного здесь, используя трюк, предложенный @chux, мы пользуемся тем фактом, что для отрицательного значения в дополнении twos соответствующее положительное значение равно побитовому отрицанию отрицательного представления плюс 1.

Это величина x может быть сдвинут бит, не сталкиваясь с зависимым от реализации поведением. После выполнения деления результат преобразуется обратно в отрицательное значение, если исходное значение было отрицательным, выполняя то же преобразование, что и раньше.

#include <stdio.h>
#include <limits.h>

int divide_2n(int x, unsigned n);

int main(void)
{
    printf("-7 / 4 = %d\n", divide_2n(-7, 2));
    printf("27 / 8 = %d\n", divide_2n(27, 3));
    printf("-27 / 8 = %d\n", divide_2n(-27, 3));
    printf("-9 / 2 = %d\n", divide_2n(-9, 1));
    printf("-9 / 1 = %d\n", divide_2n(-9, 0));

    return 0;
}

int divide_2n(int x, unsigned n)
{
    unsigned n_bits = CHAR_BIT * sizeof(int);
    unsigned neg = x & (1U << (n_bits + ~0));

    if (neg) {
        x = ~(unsigned)x + 1;
    }

    x = (unsigned)x >> n;

    if (neg) {
        x = ~x + 1;
    }

    return x;
}

-7 / 4 = -1
27 / 8 = 3
-27 / 8 = -3
-9 / 2 = -4
-9 / 1 = -9