这段代码的作用是什么？

Question

我需要将一些旧的与图形相关的C/C++代码移植到Java和JavaScript上，我发现其中有这样一段：

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

其中b代表short int类型的蓝色，同样的代码也用于r和b（红色和蓝色）。这个注释并没有什么用。

除了明显的移位和加法操作，我无法理解它的作用。我可以在不理解的情况下进行移植，只是出于好奇想要问一下。

- exebook

---

提示：位移操作可以用乘法或除法来实现。 :-) - Sourav Ghosh

那么为什么你会打上“Java”、“Javascript”、“C”和“C++”这些标签呢？ - Cory Kramer

不需要理解就能进行移植？这是一项值得珍惜的技能。 - seanhodges

不知道这些颜色值来自哪里或为什么被操纵，除非有人恰好认出某种技巧，否则很可能无法得到答案。 - Pointy

@seanhodges，当然可以在不理解算法的情况下将代码从一种语言移植到另一种语言。为什么不呢？ - user4229245

RGB的值是由6个不同的通道给出的吗？我的意思是，一个8位通道用于红色的低位部分，另一个8位通道用于红色的高位部分，以此类推。RGB的值来源是什么？图像文件、流数据... - LPs

Answer 1

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

这是一种关于除以255的固定点近似方法。从概念上讲，它对基于像素值的计算进行规范化非常有用，使得255（通常是最大像素值）恰好等于1。

它被描述为非常快速，因为完全通用的整数除法在许多CPU上是相对缓慢的操作 - 尽管如果编译器能够推断出输入约束条件，它可能会为您进行类似的优化。

其原理是基于这样一个想法：257/(256*256)是1/255的一个非常接近的近似值，且x*257/256可以表示为x+(x>>8)。+1是四舍五入支持，允许该公式在所有x值[0..65534]的情况下准确匹配整数除法x/255。

对内部部分进行一些代数运算可能会使事情更加清晰...

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

这里有更多讨论：如何快速进行alpha混合？和通过乘法进行除法计算

---

顺便说一句，如果你想要四舍五入并且你的CPU可以进行快速乘法运算，以下方法对于所有uint16_t被除数值都是准确的--实际上是[0..(2^16)+126]。

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

- Brent Bradburn

---

通常情况下，在对已经编码为8位的像素进行图像处理时，由于伽马压缩引入的非线性映射，结果通常是不正确的（但通常足够接近）。 - Brent Bradburn

与“快速乘法”相关的注释：https://dev59.com/QWw15IYBdhLWcg3w3ffN - Brent Bradburn

Answer 2

需要翻译的内容如下：

当您必须为每个像素组合许多alpha值时，您需要使用比257/256更精确的公式。举个例子，当进行图像缩小操作时，您需要将每个源像素的4个alpha值合并到目标像素中，并将所有源像素贡献到目标像素。

我发布了一个无限精度的二进制操作版本的 /255，但没有理由被拒绝。所以我会补充说明，我实现了用于生活的 alpha 混合硬件，我编写实时图形代码和游戏引擎，我在 MICRO 等会议上发表过关于这个主题的文章，所以我真的知道自己在说什么。而且对人们来说，了解比 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时，您可能没有窄乘法，因此这仍然可能更快，但需要检查。

至于那个说“为什么不使用内置的操作系统能力来进行Alpha字体渲染”的人：如果您已经在该操作系统中拥有大量图形代码库，则这可能是一个不错的选择。否则，您需要编写并调试比这段代码难得多的数百到数千行代码才能利用操作系统版本。最终，您拥有的操作系统代码根本无法移植，而这段代码可以在任何地方使用。

- user2465201

---

拒绝你对我的帖子所做的编辑的原因之一是“此次编辑偏离了帖子的原意。即使必须进行重大更改，也应该努力保留帖子所有者的目标。” 换句话说，适当的做法是编写自己的帖子，就像你现在所做的那样。 - Brent Bradburn

啊...我明白了。谢谢。 :) - user2465201

Answer 3

看起来这个代码用于检查蓝色（或红色或绿色）是否完全使用。当b等于255时，它的值为1，对于所有更低的值则为0。

- kaykay

---

如果 b 在 1 到 255 之间，那么这是有意义的。但是 (b >> 8) 总是为零... 写成 (b+1) >> 8 就足够了。 - ArnonZ

该值是一个short类型。最大值为65535（对于无符号数）。 - seanmk

那是最大的物理值。也许代码强制执行的有一个最大逻辑值。 - ArnonZ

Answer 4

计算b+1 + b/256的值，并将结果除以256。

这样，使用位移操作，编译器会使用CPU级别的移位指令来进行翻译，而不是使用FPU或库函数的除法操作。

- LPs

---

这是正确的，但它并没有真正回答为什么代码要执行那个操作的问题。 - Pointy

我认为OP完全知道>> 8就是/ 256。他们所问的是，为什么要执行这个表达式，也就是从语义上讲，它代表什么意思。 - lurker

Answer 5

我猜它正在尝试做以下事情：

boolean isBFullyOn = false;

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

在处理器速度较慢的早期，像上面这样的智能位移技巧可能比显而易见的if-then-else逻辑更快。它避免了一个代价高昂的跳转语句。

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

同时也要考虑到我的推测！

- Brett Walker

---

但是bool isFullyOn = b == 0xFF仍然会更快（假设没有编译器优化的情况下）。 - Dale Wilson

在Java中，这是正确的；但是OP正在移植一些旧的C/C++图形代码，很可能编译为针对特定CPU的目标代码，这将导致高性能的汇编代码。 - Brett Walker

@Dave，你认为快的实际上是我上面发布的代码的语法糖。它意味着汇编代码中的跳转。 - Brett Walker

是的。我发帖后不久就意识到了这一点。我想，问题的真正重点在于，将编译器修改为生成所需代码的程序员应该被要求记录：他们试图做什么，为什么认为它有效，以及他们测试的编译器版本。 - Dale Wilson

请查看@nobar发布的链接。这些类型的优化非常普遍。 - Brett Walker

Answer 6

b = (b + (b >> 8)) >> 8; 的基本意思是 b = b *257/256。

我认为+1 是对内部 >>8 导致的 -0.5 平均值减少的丑陋黑客。

我会将其写为 b = (b + 128 + ((b +128)>> 8)) >> 8;。

- user3528438

---

你的等式有误（应该是b*257/256/256），但看到你的答案让我认识到了这个公式。谢谢。 - Brent Bradburn

Answer 7

Running this test code:

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 posted。

- OldCurmudgeon