相关疑难解决方法(0)

我正在寻找一个在Java中工作的高效公式,它计算以下表达式:

(low + high) / 2

用于二进制搜索.到目前为止,我一直在使用"低+(高 - 低)/ 2"和"高 - (高 - 低)/ 2"来避免某些情况下的溢出和下溢,但不是两者都有.现在我正在寻找一种有效的方法,可以用于任何整数(假设整数范围从-MAX_INT - 1到MAX_INT).

更新:结合Jander和Peter G.的答案并进行实验一段时间我得到了中值元素及其近邻的以下公式:

最低中点(等于floor((low + high)/2),例如[2 3] - > 2,[2 4] - > 3,[-3 -2] - > -3)

mid = (low & high) + ((low ^ high) >> 1);

最高中点(等于ceil((low + high)/2),例如[2 3] - > 3,[2 4] - > 3,[-3 -2] - > -2)

low++;
mid = (low & high) + ((low ^ high) >> 1);

中 - 前点(等于 …

我看到这个Java代码可以非常有效地在两种RGB888颜色之间进行完美的50%混合:

public static int blendRGB(int a, int b) {
    return (a + b - ((a ^ b) & 0x00010101)) >> 1;
}

这显然相当于单独提取和平均通道.像这样的东西:

public static int blendRGB_(int a, int b) {
    int aR = a >> 16;
    int bR = b >> 16;
    int aG = (a >> 8) & 0xFF;
    int bG = (b >> 8) & 0xFF;
    int aB = a & 0xFF;
    int bB = b & 0xFF;
    int cR = (aR + bR) >> 1;
    int …

在围绕Compiler Explorer进行测试时，我尝试了以下无溢出函数来计算 2 个无符号 32 位整数的平均值：

uint32_t average_1(uint32_t a, uint32_t b)
{
    if(a < b){
        a ^= b;
        b ^= a;
        a ^= b;
    }
    return b + (a - b) / 2;
}

被编译成这样：（与激活的-O1, -O2,-O3优化相同）

average_1:
        cmp     edi, esi
        jnb     .L2
        mov     eax, edi
        mov     edi, esi
        mov     esi, eax
.L2:
        sub     edi, esi
        shr     edi
        lea     eax, [rdi+rsi]
        ret

其中代码的交换部分经过优化，可以使用mov具有 1 个附加寄存器的指令。

我已经阅读了这些问题：

人们为什么不使用异或交换？
通过 mov、xor 交换变量的成本

并得到：

• 使用 XOR …