LeetCode 第 231 号问题:2 的幂

栏目: 编程工具 · 发布时间: 5年前

内容简介:本文首发于公众号「五分钟学算法」,是个人网站:www.cxyxiaowu.com题目来源于 LeetCode 上第 231 号问题:2 的幂。题目难度为 Easy,目前通过率为 45.6% 。

本文首发于公众号「五分钟学算法」,是 图解 LeetCode 系列文章之一。

个人网站:www.cxyxiaowu.com

题目来源于 LeetCode 上第 231 号问题:2 的幂。题目难度为 Easy,目前通过率为 45.6% 。

题目描述

给定一个整数,编写一个函数来判断它是否是 2 的幂次方。

示例 1:

输入: 1
输出: true
解释: 2^0 = 1
复制代码

示例 2:

输入: 16
输出: true
解释: 2^4 = 16
复制代码

示例 3:

输入: 218
输出: false
复制代码

题目解析

首先,先来分析一下 2 的次方数的二进制写法:

LeetCode 第 231 号问题:2 的幂

仔细观察,可以看出 2 的次方数都只有一个 1 ,剩下的都是 0 。根据这个特点,只需要每次判断最低位是否为 1 ,然后向右移位,最后统计 1 的个数即可判断是否是 2 的次方数。

代码很简单:

class Solution {
public:
    bool isPowerOfTwo(int n) {
        int cnt = 0;
        while (n > 0) {
            cnt += (n & 1);
            n >>= 1;
        }
        return cnt == 1;
    } 
};
复制代码

该题还有一种巧妙的解法。再观察上面的表格,如果一个数是 2 的次方数的话,那么它的二进数必然是最高位为1,其它都为 0 ,那么如果此时我们减 1 的话,则最高位会降一位,其余为 0 的位现在都为变为 1,那么我们把两数相与,就会得到 0。

比如 2 的 3 次方为 8,二进制位 1000 ,那么 8 - 1 = 7 ,其中 7 的二进制位 0111。


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

新媒体文案创作与传播

新媒体文案创作与传播

秋叶、叶小鱼、勾俊伟 / 人民邮电出版社 / 2017-4 / 39.80元

《新媒体文案创作与传播》共分三篇。第1篇是新媒体文案基础篇,主要讲述了新媒体文案的基本概念、新媒体文案的岗位要求和职业能力素养;第二篇是新媒体文案创意实务篇,主要讲述了新媒体文案的创作思路、新媒体文案的写作技巧、爆款新媒体文案的打造、新媒体销售文案的写作、新媒体对文案传播的新要求、新媒体品-牌文案的写作,以及不同媒介的特征及发布形式;第三篇为新媒体文案相关技能补充,主要讲述的是策划能力。 《新媒体......一起来看看 《新媒体文案创作与传播》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具