精简代码：改换运算符

kelecn

知识

发布于：2020年8月22日

字数：997字

时长：4分钟

次浏览

简介：精简代码：改换运算符

1、位运算（&）替换取余（%）运算

即：如果Y = $2^{n}$ ,则X%Y可以变化为X&(Y-1)
由于我们知道位运算比较高效，在某些情况下，当b为2的n次方时，有如下替换公式：
a % b = a & (b-1)(b=2^n)
即：a % 2^n = a & (2^n-1)
例如：14%8，取余数，相当于取出低位，而余数最大为7，14二进制为1110，8的二进制1000，8-1 = 7的二进制为0111，由于现在低位全为1，让其跟14做&运算，正好取出的是其低位上的余数。1110&0111=110即6=14%8；（此公式只适用b=2^n，是因为可以保证b始终只有最高位为1，其他二进制位全部为0，减去1，之后，可以把高位1消除，其他位都为1，而与1做&运算，会保留原来的数。）

2、左移运算（<<）替换乘法（*）运算

a=a8;
b=b/8;
可以改为：
a=a<<3;
b=b>>3;
说明：
除2 = 右移1位；乘2 = 左移1位
除4 = 右移2位；乘4 = 左移2位
除8 = 右移3位；乘8 = 左移3位
通常如果需要乘以或除以2的n次方，都可以用移位的方法代替，大部分的C编译器,用移位的方法得到代码比调用乘除法子程序生成的代码效率高。
实际上，只要是乘以或除以一个整数才可以用移位的方法得到结果。
如：
a=a9 =a(8+1)=a8+a1
可以改为：
a=(a<<3)+a
如：
a=a7 =a(8-1)=a8-a1
可以改为：
a=(a<<3)-a

总结：a=an; n分解成(2^m + s),则a=an可以改为a=(a<<m)+as;as再同理分解替换。

例：a=a10 => a=a(8+2) => a=a8 + a2 => a=(a<<3)+(a<<1)

3、右移运算（>>）替换除法（/）运算

a=a*8;
b=b/8;
可以改为：
a=a<<3;
b=b>>3;
说明：
除2 = 右移1位；乘2 = 左移1位
除4 = 右移2位；乘4 = 左移2位
除8 = 右移3位；乘8 = 左移3位
通常如果需要乘以或除以2的n次方，都可以用移位的方法代替，大部分的C编译器,用移位的方法得到代码比调用乘除法子程序生成的代码效率高。
实际上，只要是乘以或除以一个整数才可以用移位的方法得到结果。
如：
a=a/9 =a/(8+1)=a/8+a/1
可以改为：
a=(a>>3)+a
如：
a=a/7 =a/(8-1)=a/8-a/1
可以改为：
a=(a>>3)-a
总结：a=a/n; n分解成(2^m + s),则a=a/n可以改为a=(a>>m)+a/s;a/s再同理分解替换。
例：a=a/10 => a=a/(8+2) => a=a/8 + a/2 => a=(a>>3)+(a>>1)

4、C/C++中的移位操作容易出错的情况：

什么样的数据类型可以直接移位
只有整型数据才能用移位替代乘除法，如：char、short、int、long、unsigned char、unsigned short、unsigned int、unsigned long。（double、float、bool、long double则不可以进行移位操作。）
有符号数据类型移位需要注意符号位
对于char、short、int、long这些有符号的数据类型：
对负数进行左移：符号位始终为1，其他位左移。
对正数进行左移：所有位左移，即 <<，可能会变成负数
对负数进行右移：取绝对值，然后右移，再取相反数
对正数进行右移：所有位右移，即 >>
无符号数据类型的移位操作
对于unsigned char、unsigned short、unsigned int、unsigned long这些无符号数据类型：
没有特殊要说明的，使用<< 和 >> 操作符就OK了。
5、参考资料：
使用位运算替换取余操作
移位操作与乘除法的关系