c - C 中的 Bit Twiddling - 计算 2 倍 x 或返回最大有符号数

Question

我正在编写一个计算参数 x 的 2 倍的函数，但如果它溢出，它应该返回最大的正数或负数。问题是我只能使用 ! ~ & ^ | + << >> .涉及 32 位整数。

这是我目前所拥有的:

int boundedMult(int x){
    int xSign = x>>31
    int y = x << 1; // Multiply by 2
    int signBit = y>>31; // Capture the signBit of the answer
    int shift = signBit; 
    shift |= shift<<1; // Make shift all 1 or 0 depending on the sign bit
    shift |= shift<<2;
    shift |= shift<<4;
    shift |= shift<<8;
    shift |= shift<<15;
    int answer = ~signBit<<31 | shift; // 01111... If signBit=1 and 1000... If signBit=0
}

看起来不错，对吧？我也不能使用无符号字节 (0-255) 以外的任何常量，包括在内。我尝试了很多方法，但最终我在所有这些方法中都违反了其中一条规则。

Answer 1

有趣的挑战!这是我的解决方案，我希望我没有错误地违反任何约束:

#include <stdio.h>
#include <stdint.h>

// work with uint to avoid undefined behavior (signed int overflow is undefined)
static inline int32_t x2(int32_t v) {
    uint32_t uv = v;
    // our first option: "multiply" by shifting:
    uint32_t doubled = uv<<1;

    // our second option: clamp to max/min integer:
    uint32_t neg     = !!(uv >> 31); // 1 if negative
    uint32_t bigval  = (~0u)>>1;     // 0x7fffffff
    uint32_t clamped = bigval + neg; // 0x80000000 if neg, 0x7fffffff otherwise

    // so, which one will we use?
    uint32_t ok   = !((v>>31) ^ (v>>30)); // 0 if overflow, 1 otherwise
                                          // note the use of signed value here
    uint32_t mask = (~ok)+1; // 0x00000000 if overflow, 0xffffffff otherwise

    // choose by masking one option with ones, the other with zeroes
    return (mask & doubled) | ((~mask) & clamped);
}

static inline void check(int32_t val, int32_t expect) {
    int32_t actual = x2(val);
    if ((val & 0x3ffffff) == 0) {
        printf("0x%08x...\n", val);
    }
    if (actual != expect) {
        printf("val=%d, expected=%d, actual=%d\n", val, expect, actual);
    }
}

int main() {
    int32_t v = 0x80000000;

    printf("checking negative clamp...\n");
    for (; v < -0x40000000; ++v) {
        check(v, 0x80000000);
    }

    printf("checking straight double...\n");
    for(; v < 0x40000000; ++v) {
        check(v, 2*v);
    }

    printf("checking positive clamp...\n");
    for(; v < 0x7fffffff; ++v) {
        check(v, 0x7fffffff);
    }
    check(0x7fffffff, 0x7fffffff);

    printf("All done!\n");
    return 0;
}

它似乎工作正常:

gcc -std=c99 -O2 -Wall -Werror -Wextra -pedantic bounded.c -o bounded && ./bounded
checking negative clamp...
0x80000000...
0x84000000...
0x88000000...
0x8c000000...
0x90000000...
0x94000000...
0x98000000...
0x9c000000...
0xa0000000...
0xa4000000...
0xa8000000...
0xac000000...
0xb0000000...
0xb4000000...
0xb8000000...
0xbc000000...
checking straight double...
0xc0000000...
0xc4000000...
0xc8000000...
0xcc000000...
0xd0000000...
0xd4000000...
0xd8000000...
0xdc000000...
0xe0000000...
0xe4000000...
0xe8000000...
0xec000000...
0xf0000000...
0xf4000000...
0xf8000000...
0xfc000000...
0x00000000...
0x04000000...
0x08000000...
0x0c000000...
0x10000000...
0x14000000...
0x18000000...
0x1c000000...
0x20000000...
0x24000000...
0x28000000...
0x2c000000...
0x30000000...
0x34000000...
0x38000000...
0x3c000000...
checking positive clamp...
0x40000000...
0x44000000...
0x48000000...
0x4c000000...
0x50000000...
0x54000000...
0x58000000...
0x5c000000...
0x60000000...
0x64000000...
0x68000000...
0x6c000000...
0x70000000...
0x74000000...
0x78000000...
0x7c000000...
All done!

使用 this handy interactive compiler ，我们可以得到各种平台的反汇编。带注释的 ARM64 程序集:

x2(int):
        asr     w1, w0, 30         # w1 = v >> 30
        cmp     w1, w0, asr 31     # compare w1 to (v>>31)
        csetm   w1, eq             # w1 = eq ? 0 : -1
                                   # --- so w1 is "mask"
        mov     w2, 2147483647     # w2 = 0x7fffffff
        mvn     w3, w1             # w3 = ~w1
                                   # --- so w3 is ~mask
        add     w2, w2, w0, lsr 31 # w2 = w2 + (v>>31)
                                   # --- so w2 is "clamped"
        and     w2, w3, w2         # w2 = w3 & w2
        and     w0, w1, w0, lsl 1  # w0 = w1 & (v << 1)
        orr     w0, w2, w0         # w0 = w2 | w0
        ret                        # return w0

在我看来效率很高。非常棒的是，“doubled”永远不会保存到寄存器中——它只是作为 和 指令之一的输入值的移位完成的。