(r+1 + (r >> 8)) >> 8 是做什么的？

Question

在一些旧的 C/C++ 图形相关代码中，我必须移植到 Java 和 JavaScript 我发现了这个：

b = (b+1 + (b >> 8)) >> 8; // very fast

其中 b 是蓝色的 short int，r 和 b（红色和蓝色）的代码相同。评论没有帮助。

除了明显的移动和添加之外，我无法弄清楚它的作用。不懂也可以移植，我只是好奇问一下

Answer 1

是b+1 + b/256的值，这个计算除以256。

这样，编译器使用CPU电平移位指令进行位移位，而不是使用FPU或库除法函数。

Answer 2

我怀疑它正在尝试执行以下操作：

boolean isBFullyOn = false;

if (b == 0xff) {
  isBFullyOn = true;
}

回到处理器速度慢的时代；像上面这样的智能移位技巧可能比明显的 if-then-else 逻辑更快。它避免了代价高昂的跳转语句。

它可能还在处理器中设置了一个溢出标志，用于后面的一些逻辑。这完全取决于目标处理器。

我也是投机者！！

Answer 3

看起来是为了检查 blue（或 red 或 green）被充分利用。当 b 为 255 时，它的计算结果为 1，对于所有较低的值，它的计算结果为 0。

Answer 4

b = (b + (b >> 8)) >> 8; 基本上是 b = b *257/256 .

我认为 +1 是对 -0.5 均值减少的丑陋破解，由内部 >>8.

我会写成b = (b + 128 + ((b +128)>> 8)) >> 8;。

Answer 5

运行本次测试代码：

public void test() {
    Set<Integer> results = new HashSet<Integer>();
    // short int ranges between -32767 and 32767
    for (int i = -32767; i <= 32767; i++) {
        int b = (i + 1 + (i >> 8)) >> 8;
        if (!results.contains(b)) {
            System.out.println(i + " -> " + b);
            results.add(b);
        }
    }
}

生成 -129 和 128 之间的所有可能值。但是，如果您使用 8 位颜色 (0 - 255)，那么唯一可能的输出是 0（对于 0 - 254）和 1（对于 255 ) 所以它很可能正在尝试函数 @kaykay .

Answer 6

y = ( x + 1 + (x>>8) ) >> 8 // very fast

这是除以 255 的定点近似值。从概念上讲，这对于基于像素值的标准化计算非常有用，这样 255（通常是最大像素值）正好映射到 1。

它被描述为非常快，因为完全通用的整数除法在许多 CPU 上是一个相对较慢的操作——尽管您的编译器可能会如果它可以推断出输入约束，则为您提供类似的优化。

这是基于 257/(256*256) 非常接近 1/255 并且 x*257/256 可以表示为 x+(x>>8) 的想法。 +1 是舍入支持，它允许公式与 [0..65534] 中 x 的所有值的整数除法 x/255 完全匹配.

内部的一些代数可能会使事情更清楚一些...

       x*257/256
     = (x*256+x)/256
     = x + x/256
     = x + (x>>8)

此处讨论较多：How to do alpha blend fast? and here: Division via Multiplication

顺便说一句，如果你想要舍入到最近的值，并且你的 CPU 可以进行快速乘法运算，那么以下对于所有 uint16_t 股息值都是准确的 - 实际上 [0.. (2^16)+126].

y = ((x+128)*257)>>16 // divide by 255 with round-to-nearest for x in [0..65662]

Answer 7

当您想要使用比 257/256 更准确的公式时，一个常见的用例是您必须将每个像素的大量 alpha 值组合在一起。例如，在进行图像缩小时，您需要为每个对目标有贡献的源像素组合 4 个 alpha，然后组合对目标有贡献的所有源像素。

我发布了一个无限精确的 /255 位旋转版本，但它被无故拒绝了。所以我要补充一点，我以实现 alpha 混合硬件为生，我以编写实时图形代码和游戏引擎为生，我已经在像 MICRO 这样的会议上发表了关于这个主题的文章，所以我真的知道我在做什么谈论。并且它可能对人们有用或至少有趣，以了解更准确的公式，即 EXACTLY 1/255：

版本 1：x = (x + (x >> 8)) >> 8 - 没有添加常量，不会满足 (x * 255) / 255 = x，但在大多数情况下看起来很好。版本 2：x = (x + (x >> 8) + 1) >> 8 - 将满足 (x * 255) / 255 = x 的整数，但不会为所有 alpha 找到正确的整数值

版本 3：（简单整数舍入）： (x + (x >> 8) + 128) >> 8 - 不会为所有 alpha 找到正确的整数值，但在相同的成本下平均会比版本 2 更接近。

版本 4：无限精确版本，可达到所需的任何精度级别，适用于任意数量的复合 alpha：（对图像大小调整、旋转等很有用）：

[(x + (x >> 8)) >> 8] + [ ( (x & 255) + (x >> 8) ) >> 8]

为什么版本 4 无限准确？因为 1/255 = 1/256 + 1/65536 + 1/256^3 + 1/256^4 + ...

上面最简单的表达式（版本 1）不处理舍入，但它也不处理从无限数量的相同总和列中出现的进位。上面添加的新项决定了这个无限数量的 256 基数的进位（0 或 1）。通过添加它，您将获得与添加所有无限加数相同的结果。在这一点上，您可以通过将半位添加到您想要的任何精度点来舍入。

OP 可能不需要，但人们应该知道您根本不需要近似。上面的公式其实比双精度浮点数更准确

至于速度：在硬件中，此方法甚至比单个（全角）添加更快。在软件中，您必须考虑吞吐量与延迟。在延迟方面，它可能仍然比窄乘法快（肯定比全宽度乘法快），但在 OP 上下文中，您可以一次展开许多像素，并且由于现代乘法单元是流水线式的，所以您仍然可以。在转换为 Java 时，您可能没有窄乘法，所以这仍然可以更快，但需要检查。

WRT 那个说 "why not use the built in OS capabilities for alpha blitting?" 的人：如果您在那个 OS 中已经有大量的图形代码库，这可能是一个不错的选择。如果没有，您将查看成百上千行代码来利用 OS 版本 - 编写和调试的代码比此代码难得多。最后，您拥有的 OS 代码根本不可移植，而此代码可以在任何地方使用。

(r+1 + (r >> 8)) >> 8 是做什么的？

what (r+1 + (r >> 8)) >> 8 does?

c

bit-manipulation