1

我只能用！~ & ^ | + << >>

我正在用 C 写这个。

我正在尝试将数字 x 除以 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));
4

2 回答 2

3

假设有符号整数的二进制补码表示和运算符的算术移位行为>>，答案可能是：

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 位，因此掩码变为全 1（即0xFFFFFFFF）或全零，然后用于保留或消除((1 << n) - 1)加法。括号&是必要的，因为加法的优先级高于按位与。

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。

于 2017-01-31T23:30:49.673 回答
1

这是一种避免移位负值的解决方案。它确实假设二进制补码表示，但它不使用一元负运算符。

位掩码用于在为负数时设置neg为非零值，如果为非负数则设置为零。这里使用@Grzegorz Szpetkowski建议的一个技巧来避免减1：改为添加。如果为负，则 的值变为 的大小。为了避免在这里使用一元负数，使用@chux建议的技巧，我们利用这样一个事实，即对于二进制补码中的负值，相应的正值等于负表示的按位否定加 1。xx~0xxx

这个量级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
于 2017-02-01T02:02:49.300 回答