用位运算优化和精简代码。

那个,转载的请放上此地出处哦~
(未完待续,还会补上数学公式图形)

咱最熟悉的就是十进制了,但咱最好的朋友计算机它最熟悉的是二进制。
它可以很潇洒地甩出一行二进制0110 0100,估计很少有人能一下看懂是十进制的什么数(100)。
不过,从二进制转换到十进制可以这么写:
2^0 * b0 + 2^1 * b1 + … + 2^n * bn (式1)
其中n为比特位,bn为n比特位的值(0或1)。
咱就靠这个公式来翻译一下吧。

但是除了翻译知道这个数是多少(以咱可以理解的形式,例如十进制)外,
位运算还能用来干吗?对咱有用吗?
有用,用来计算,位运算比普通运算要快几百倍甚至更高。

那好,咱先从最基本的位移运算开始。仅针对整数哦,浮点数由于结构特性,不在此文讨论范畴。
在二进制里,最左代表最高位,最右代表最低位。
同时根据式1可以得出结论,bn不为1(即0)的单元,完全不受任何位移运算影响,因此全部忽略。

先谈谈左移。
左移就是将所有位向高处移动,左移一位即将所有字节向高处移一位。
左移有一个特点,如果移位超过限制,即会发生溢出。当然,安全的左移,是直接删除此位的。

原始值:2^0 * b0 + 2^1 * b1 + … + 2^n * bn
左移x位:2^x * b0 + 2^(x+1) * b1 + … + 2^(x+n) * bn

左移x位后的表达式中每一单元,均是原始值中对应单元的2^x倍。
所以简单来说,左移x位,产生的结果就是2^x*原始值。

再谈谈右移。
右移就是将所有位向低处移动,右移一位即将所有字节向低处移一位。
右移也有一个特点,即移动x位,就会把最低的x位全部丢弃(因为最低位是0位,再往下,就木有了^_^)。

原始值:2^0 * b0 + 2^1 * b1 + … + 2^n * bn
右移x位:0 * x + … + 2^(n-x) * bn

右移x后,所有低于x的单元,均为0,而所有其他单元,均比原始值相应单元小2^x倍。
所以,右移x位后产生的结果比较复杂,有两个部分,n小于x的单元和为0,n大于等于x的单元和是原始值n大于等于x的单元和的2^x倍。

从上面看,左移比较有用,因为它可以得出我们需要的确定值,这样想乘以2的指数倍时,可以使用位运算来提高效率。
例如:
1000 * 2 = 1000 << 1
1000 * 32 = 1000 << 5

 

那右移的用处在哪儿呢?

移动了x位,有x个不确定项,嗯,这是个难题。

但是换一种思路,n大于等于x的单元,位移后全部比原始值对应单元小2^x倍。

而位移后n小于x的单元被删除,即等同于0无效化,其实也能视为比原始值对应单元小无限倍(趋于无穷大,因此为0)。

所以,当我们近似认为,n小于x的单元,位移后全部比原始值对应单元小2^x倍时。

原始值:2^0 * b0 + 2^1 * b1 + … + 2^n * bn

右移x位近似:2^(-x) * b0 + 2^(1-x) * b1 + … + 2^(n-x) * bn

暂时无视bn,假设所有bn均为1,制造误差最大条件,

由此产生的误差:- 2^(-1) – 2^(-2) – … – 2^(-x)

依据求和公式,对误差求和,

S = ( -2^(-1) * ( 2^(-x+1) – 1 ) ) / ( 2^(-1) – 1 ) = 2^(-x) – 1,

当x=1时,S最大值为-0.5,当x趋向无穷时,S最小趋向为-1。

即在假设所有位均为1的最坏情况下,右移近似误差在(-1,-0.5]范围内。

 

好啦,到此咱可以得出结论啦, 右移x位近似可以等同原始值除以2^x,并且误差在-1到-0.5之间,因此通常情况下的右移x位,等于原始值除以2^x并向下求整。

即 NUMBER >> x = Math.floor( NUMBER /  (2 ^ x) )

不过若x很大,原始值中低于x的位中为1的又较多,那么在可以被除尽的场合,依然会因为误差-1,而错误地减去1。

 

未完待续……:mrgreen:

发表评论

电子邮件地址不会被公开。 必填项已用*标注