深入探讨用位掩码代替分支(1):利用带符号移位生成掩码

前端之家收集整理的这篇文章主要介绍了深入探讨用位掩码代替分支(1):利用带符号移位生成掩码前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

  几年前我写了一篇“优化分支代码——避免跳转指令堵塞流水线”(http://www.jb51.cc/article/p-etmlkbgq-uh.html)。因当时是整理笔记,有些粗略。这几年又有了新的心得,故决定深入探讨,顺便回答网友评论

  housisong(http://blog.csdn.net/housisong)提到了用利用带符号移位生成掩码——
(假设n是32bit有符号数): (n>>31) 当n>=0的时候结果为0x00000000,当n<0时得到0xFFFFFFFF掩码,然后利用该掩码来合并分支。

  这是一个很好的思路,避免了状态寄存器访问。
  但该方案也有局限性——
1.某些编程语言(如VB6)没有带符号移位运算符。
2.仅能判断与0比较。但在很多时候,我们需要得到特定整数比较后的掩码。

  没有带符号移位运算符,问题不大。现在主流编程语言大多支持带符号移位。比如微软打造了VB.Net,支持带符号移位。
  计算特定整数比较后的掩码,最简单的就是前文所用的方法——根据“C语言比较运算的的结果是0和1”生成掩码。但现在已经知道该方法会访问状态寄存器,影响效率。有没有不依赖状态寄存器的办法呢?

  其中有一个思路就是利用减法,将“与特定整数的比较”转换为“与0的比较”。但这样做有时会产生溢出,导致运算结果不正确 或抛出异常(当检查整数溢出异常时)。如果再做溢出处理的话,增加了复杂度、影响效率。
  我曾因这个难题困扰很久。后来突然想到,在某些时候,其实并不需要处理溢出问题。

  因图像处理中最常用的带符号类型是16位整数,所以我在这里采用16位带符号整数(signed short),在计算掩码时应右移15位。


一、计算掩码

1.1 与0比较

  我们先热身一下,回顾一下与0比较时的掩码算法——
MASK = n>>15// “<0”时全1,“>=0”时全0

  加一个取反运算符后,可以得到这样的掩码——
MASK = ~(n>>15)// “>=0”时全1,“<0”时全0

  如先对n求负,可以得到这样的掩码——
MASK = (-n)>>15// “>0”时全1,“<=0”时全0
注意:会产生溢出。这是因为整数一般是采用补数表示法的,对于16位带符号数来说,值域为 [-32768,32767],无法表示正数的32768。若忽略整数溢出异常,对-32768求负结果是-32768,进行带符号移位后会变为全1,与“>0”的设想不符。

  再加一个取反运算符后,可以得到这样的掩码——
MASK = ~((-n)>>15)// “<=0”时全1,“>0”时全0
注意:当n为-32768时会产生溢出。


1.2 与X的比较

  上面的式子虽然是与0比较,但因式中没有写0,理解起来有点吃力。于是现在将0补上——
MASK = (n-0)>>15// “<0”时全1,“>=0”时全0
MASK = ~((n-0)>>15)// “>=0”时全1,“<0”时全0
MASK = (0-n)>>15// “>0”时全1,“<=0”时全0
MASK = ~((0-n)>>15)// “<=0”时全1,“>0”时全0

  观察上式,我们可以将0替换为任意整数X——
MASK = (n-X)>>15// “<X”时全1,“>=X”时全0
MASK = ~((n-X)>>15)// “>=X”时全1,“<X”时全0
MASK = (X-n)>>15// “>X”时全1,“<=X”时全0
MASK = ~((X-n)>>15)// “<=X”时全1,“>X”时全0

  因为现在是任意整数X,在进行减法运算时有可能产生溢出。


二、饱和处理

  在编写图像处理程序时,经常出现RGB值超过[0,255]范围的情况。这时,得做饱和处理,将越界数值饱和到边界,即这样的代码
if (r < 0) r = 0;
if (r > 255) r = 255;

  现在我们将利用位运算,来优化这样的代码

2.1 “<0”时的处理

  我们可以利用与运算将数值修正为0,应选用【“>=0”时全1,“<0”时全0】的掩码。语句为——
MASK = ~(n>>15)// “>=0”时全1,“<0”时全0
m = n & MASK

  将其整理为一条表达式——
m = n & ~(n>>15)

  因为该式没有用到减法,所以当n为任意值时都不会溢出。

2.2 “>255”时的处理

  我们可以利用或运算,将超过范围的数值修正为全1。再将其与0xFF进行与运算,将超过范围的数值修正为255,这是根据255(0xFF)正好是低8位。

  怎么判断超过范围呢?有三种策略——
A.“>255”。标准方式。
B.“>=256”。因整数的连续性。
C.“>=255”。因255进行饱和处理后,结果仍是255。

  因现在为了避免状态寄存器,不能利用比较语句,只能利用前面的位掩码算法。列出三种策略是为了找到效率最高的方案。
  回顾一下“1.2 与X的比较”,找出判断“>X”、“>=X”的式子——
MASK = ~((n-X)>>15)// “>=X”时全1,“<X”时全0
MASK = (X-n)>>15// “>X”时全1,“<=X”时全0

  进过对比后发现,判断“>X”的运算量最少,所以我们应选择策略A。语句为——
MASK = (255-n)>>15
m = (n | MASK) & 0xFF

  将其整理为一条表达式——
m = (n | ((255-n)>>15)) & 0xFF

  注意该式仅在n大于等于0时有效。

2.3 饱和处理

  现在开始考虑实际的饱和处理,即将“<0”的修正为0,又将“>255”的修正为255。

  先整理一下上面的成果——
m = n & ~(n>>15)// “<0”时的处理。n为任意值时都有效。
m = (n | ((255-n)>>15)) & 0xFF// “>255”时的处理。仅在n大于等于0时有效。

  因“>255”处理在n小于0时无效,而“<0”处理在任何时候有效。所以我们可以先进行>255”处理,再进行“<0”处理,以屏蔽中间的错误值。语句为——
m = ( (n | ((255-n)>>15)) & ~(n>>15) ) & 0xFF

  分析——
当n<0时:虽然“(n | ((255-n)>>15))”的值无效,但因“~(n>>15)”的值为0,进行“& ~(n>>15)”运算后,结果为0。
当n>=0且n<=255时:“((255-n)>>15)”的值为0,“| ((255-n)>>15)”会保留原值。“~(n>>15)”的值为全1,“& ~(n>>15)”也会保留原值。
当n>255时:“((255-n)>>15)”的值为全1,“~(n>>15)”的值也为全1,最后遇到“& 0xFF”,结果为255。

  由于我们一般是将结果保存到一个BYTE型变量中,进行一次强制类型转换就行了,不需要“& 0xFF”——
m = (BYTE)( (n | ((255-n)>>15)) & ~(n>>15) )


三、实际运用

  在实际运用,上述代码比较长不易维护。可以将其封装为宏,并顺便推广一下——
#define LIMITSW_FAST(n,bits) ( ( (n) | ((signed short)((1<<(bits)) - 1 - (n)) >> 15) ) & ~((signed short)(n) >> 15) )
#define LIMITSW_SAFE(n,bits) ( (LIMITSW_FAST(n,bits)) & ((1<<(bits)) - 1) )

  bits代表限制多少位,如BYTE就是8——
#define LIMITSW_BYTE(n) ((BYTE)(LIMITSW_FAST(n,8)))


四、测试代码

  测试代码如下——

// 用位掩码做饱和处理.用求负生成掩码
#define LIMITSU_FAST(n,bits) ( (n) & -((n) >= 0) | -((n) >= (1<<(bits))) )
#define LIMITSU_SAFE(n,bits) ( (LIMITSU_FAST(n,bits)) & ((1<<(bits)) - 1) )
#define LIMITSU_BYTE(n) ((BYTE)(LIMITSU_FAST(n,8)))

// 用位掩码做饱和处理.用带符号右移生成掩码
//#define LIMITSW_FAST(n,bits) ( (n) & ~((signed short)(n) >> 15) | ((signed short)((1<<(bits)) - 1 - (n)) >> 15) )
#define LIMITSW_FAST(n,bits) ( ( (n) | ((signed short)((1<<(bits)) - 1 - (n)) >> 15) ) & ~((signed short)(n) >> 15) )
#define LIMITSW_SAFE(n,bits)) & ((1<<(bits)) - 1) )
#define LIMITSW_BYTE(n) ((BYTE)(LIMITSW_FAST(n,8)))

signed short	buf[0x10000];	// 将数值放在数组中,避免编译器过度优化

int main(int argc,char* argv[])
{
	int i;	// 循环变量(32位)
	signed short n;	// 当前数值
	signed short m;	// 临时变量
	BYTE	by0;	// 用if分支做饱和处理
	BYTE	by1;	// 用位掩码做饱和处理.用求负生成掩码
	BYTE	by2;	// 用位掩码做饱和处理.用带符号右移生成掩码

	//printf("Hello World!\n");
	printf("== noifCheck ==\n");

	// 初始化buf
	for(i=0; i<0x10000; ++i)
	{
		buf[i] = (signed short)(i - 0x8000);
		//printf("%d\n",buf[i]);
	}

	// 检查 “<0”处理
	printf("[Test: less0]\n");
	for(i=0; i<0x8100; ++i)	// [-32768,255]
	//for(i=0x7FFE; i<=0x8002; ++i)	// [-2,2]
	{
		// 加载数值
		n = buf[i];

		// 用if分支做饱和处理
		m = n;
		if (m < 0) m = 0;
		by0 = (BYTE)m;

		// 用位掩码做饱和处理.用求负生成掩码
		by1 = (BYTE)(n & -(n >= 0));
		if (by1 != by0)	printf("[Error] 1.1 neg: [%d] %d!=%d\n",n,by0,by1);	// 验证

		// 用位掩码做饱和处理.用带符号右移生成掩码
		by2 = (BYTE)(n & ~((signed short)n >> 15));
		if (by2 != by0)	printf("[Error] 1.2 sar: [%d] %d!=%d\n",by2);	// 验证
	}

	// 检查 “>255”处理
	printf("[Test: great255]\n");
	for(i=0x8000; i<0x10000; ++i)	// [0,32767]
	//for(i=0x80FE; i<=0x8102; ++i)	// [254,258]
	{
		// 加载数值
		n = buf[i];

		// 用if分支做饱和处理
		m = n;
		if (m > 255) m = 255;
		by0 = (BYTE)m;

		// 用位掩码做饱和处理.用求负生成掩码
		by1 = (BYTE)(n | -(n >= 256) );
		if (by1 != by0)	printf("[Error] 2.1 neg: [%d] %d!=%d\n",by1);	// 验证

		// 用位掩码做饱和处理.用带符号右移生成掩码
		by2 = (BYTE)(n | ((signed short)(255-n) >> 15));
		if (by2 != by0)	printf("[Error] 2.2 sar: [%d] %d!=%d\n",by2);	// 验证
	}

	// 检查 饱和处理
	printf("[Test: saturation]\n");
	for(i=0; i<0x10000; ++i)	// [-32768,32767]
	//for(i=0x7FFE; i<=0x8102; ++i)	// [-2,258]
	{
		// 加载数值
		n = buf[i];

		// 用if分支做饱和处理
		m = n;
		if (m < 0) m = 0;
		else if (m > 255) m = 255;
		by0 = (BYTE)m;

		// 用位掩码做饱和处理.用求负生成掩码
		by1 = LIMITSU_BYTE(n);
		if (by1 != by0)	printf("[Error] 3.1 neg: [%d] %d!=%d\n",by1);	// 验证

		// 用位掩码做饱和处理.用求负生成掩码
		by2 = LIMITSW_BYTE(n);
		if (by2 != by0)	printf("[Error] 3.2 sar: [%d] %d!=%d\n",by2);	// 验证
	}

	return 0;
}


  测试结果——

全部通过!

原文链接:https://www.f2er.com/vb/260175.html

猜你在找的VB相关文章