她理财 App
保险精选
3的n次方
如果让你求解 3 的 n 次方，并且不能使用系统自带的 pow 函数，你会怎么做呢？这还不简单，连续让 n 个 3 相乘就行了，代码如下：
int pow(int n){ int tmp = 1; for(int i = 1; i <= n; i++) { tmp = tmp * 3; } return tmp; } 复制代码不过你要是这样做的话，我只能呵呵，时间复杂度为 O(n) 了，怕是小学生都会！如果让你用位运算来做，你会怎么做呢？
我举个例子吧，例如 n = 13，则 n 的二进制表示为 1101, 那么 3 的 13 次方可以拆解为:
3^1101 = 3^0001 * 3^0100 * 3^1000。
我们可以通过 & 1和 >>1 来逐位读取 1101，为1时将该位代表的乘数累乘到最终结果。直接看代码吧，反而容易理解：
int pow(int n){ int sum = 1; int tmp = 3; while(n != 0){ if(n & 1 == 1){ sum *= tmp; } tmp *= tmp; n = n >> 1; } return sum; } 复制代码时间复杂度近为 O(logn)，而且看起来很牛逼。
这里说一下，位运算很多情况下都是很二进制扯上关系的，所以我们要判断是否是否位运算，很多情况下都会把他们拆分成二进制，然后观察特性，或者就是利用与，或，异或的特性来观察，总之，我觉得多看一些例子，加上自己多动手，就比较容易上手了。所以呢，继续往下看，注意，先别看答案，先看看自己会不会做。
作者：帅地
链接：https://juejin.im/post/5cdce78d5188250d8b2df3a7
来源：掘金
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
还没有人回复，赶紧来抢沙发啦~
