首页 > 代码库 > 得到1的最少运算次数
得到1的最少运算次数
例子：
func(7) = 4，可以证明最少需要4次运算
n = 7
n-1 6
n/2 3
n-1 2
n/2 1
要求：实现函数(实现尽可能高效) int func(unsign int n)；n为输入，返回最小的运算次数。给出思路(文字描述)，完成代码，并分析你算法的时间复杂度。
1 #include<iostream> 2 using namespace std; 3 4 int func(unsigned int n){ 5 6 int res = 0; 7 while(n != 1){ 8 if(n & 1 == 0) {//末尾为0，直接右移 9 n /= 2;10 res++;11 }12 else if( n & 7 == 7) {13 //末3位为1加一（因为序列内部的11收支平衡；序列头部的111收支平衡；更长的序列正收益更大）14 n++;15 n /= 8;16 res += 4;17 } else{18 //末3位不全为1则减一（序列内部的11收支平衡，加一减一均可）19 n--;20 n /= 2;21 res += 2; //一次自减一次右移22 }23 }24 return res;25 }26 27 int main(){28 printf("%d\n", func(100));29 return 0;30 }
得到1的最少运算次数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。