漫画算法:判断2的乘方

简介: 题目:实现一个方法,判断一个正整数是否是2的乘方(比如16是2的4次方,返回True;18不是2的乘方,返回False)。要求性能尽可能高。



640.jpg640.jpg640.jpg640.jpg

小灰陷入了回忆当中......



640.jpg640.jpg640.jpg



题目:


实现一个方法,判断一个正整数是否是2的乘方(比如16是2的4次方,返回True;18不是2的乘方,返回False)。要求性能尽可能高。

640.jpg640.jpg

解法一:


创建一个中间变量Temp,初始值是1。然后进入一个循环,循环中每次让Temp和目标整数比较,如果相等,则说明目标整数是2的乘方;如果不相等,则让Temp增大一倍,继续循环比较。当Temp大于目标整数时,说明目标整数不是2的乘方。

如果目标整数的大小是N,则此方法的时间复杂度是O(LogN)。

640.jpg640.jpg


640.jpg640.jpg640.jpg640.jpg640.jpg640.jpg640.jpg640.jpg


小灰的回忆到此结束......


640.jpg640.jpg640.jpg640.jpg640.jpg640.jpg640.jpg640.jpg640.jpg640.jpg640.jpg640.jpg640.jpg640.jpg


解法二:


非常有趣也非常简单的解法。因为2的乘方都符合一个规律,即 N&N-1 等于 0,所以直接用这个规律判断即可。该算法时间复杂度是O(1)。

640.jpg640.jpg640.jpg

思考题:


实现一个方法,求出一个正整数转换成二进制后的数字“1”的个数。要求性能尽可能高。

640.jpg

相关文章
|
7月前
|
存储 算法 数据可视化
【漫画算法】哈希表:古代皇帝的秘密魔法书
【漫画算法】哈希表:古代皇帝的秘密魔法书
|
7月前
|
算法 搜索推荐 数据可视化
【漫画算法】插入排序:插入宝石的传说
【漫画算法】插入排序:插入宝石的传说
|
7月前
|
算法 搜索推荐 数据可视化
【漫画算法】指挥官的排序战术:快速排序算法解密
【漫画算法】指挥官的排序战术:快速排序算法解密
|
8月前
|
算法
时间复杂度与空间复杂度(自漫画算法)
时间复杂度与空间复杂度(自漫画算法)
46 0
|
算法 JavaScript 前端开发
判断链表中是否又环使用JavaScript解决算法问题
判断链表中是否又环使用JavaScript解决算法问题
161 0
判断链表中是否又环使用JavaScript解决算法问题
|
缓存 算法 Java
如何判断对象是否该被回收(引用计数法、可达性分析算法)
概述 垃圾收集器需要完那些内存需要回收? 什么时候回收? 如何回收?
111 0
如何判断对象是否该被回收(引用计数法、可达性分析算法)
|
算法 索引
【切图仔的算法修炼之旅】LeetCode141:判断链表是否有环
【切图仔的算法修炼之旅】LeetCode141:判断链表是否有环
117 0
【切图仔的算法修炼之旅】LeetCode141:判断链表是否有环
|
算法
【漫画算法学习笔记】第二章——2.1数组
本篇博客总结了《漫画算法》第二章的知识点,并将数组的扩容封装成了工具类
106 0
【漫画算法学习笔记】第二章——2.1数组
|
算法
【牛客刷题-算法】NC4 判断链表中是否有环
【牛客刷题-算法】NC4 判断链表中是否有环
127 0
【牛客刷题-算法】NC4 判断链表中是否有环
|
算法 C语言
【牛客刷题-算法】NC141 判断是否为回文字符串
【牛客刷题-算法】NC141 判断是否为回文字符串
108 0
【牛客刷题-算法】NC141 判断是否为回文字符串

热门文章

最新文章