什么(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

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/255对于的所有值x在[0..65534].

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

       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]