【C++算法基础】利用位运算来判断一个数的奇偶性

作者：刘扬俊
原文链接：https://blog.csdn.net/qq_19782019/article/details/85621386

今天看到一个大佬的快速幂算法，全程跪着看完的，大佬的优化一步一步榨干性能，从18秒到0秒的优化真的是让我跪着站不起来了。。。下面我做一个笔记记录一下我觉得比较实用的优化小技巧。

在C语言中，power%2==1可以用更快的“位运算”来代替，power&1。

因为如果power为偶数，则其二进制表示的最后一位一定是0；
如果power是奇数，则其二进制表示的最后一位一定是1。

将他们分别与1的二进制做“与”运算，得到的就是power二进制最后一位的数字了，是0则为偶数，是1则为奇数。
例如5是奇数，则5&1=1；而6是偶数，则6&1=0；因此奇偶数的判断就可以用“位运算”来替换了。

同样，对于power=power/2来说，也可以用更快的“位运算”进行替代，我们只要把power的二进制表示向右移动1位就能变成原来的一半了。

本文地址：https://blog.csdn.net/qq_39072627/article/details/107400478