leetcode-231-Power of Two

题目描述:

Given an integer, write a function to determine if it is a power of two.

要完成的函数:

bool isPowerOfTwo(int n) 

说明:

1、给定一个int型整数,判断它是不是2的幂。首先我们可以确定负数和0都不是2的幂。1是2的0次幂。

2、如果一个数是2的幂的话,那么它可以一直除以2,直到最后等于1。如果在除以2的过程中,不能再除以2了,也就是变成了一个奇数,那么它不是2的幂。

   根据上述方法,我们可以构造出如下简单的代码:

    bool isPowerOfTwo(int n) 
    {
        if(n==0) return false;
        else if(n==1) return true;
        while(n!=1)
        {
            if(n%2==0)
                n=n/2;
            else
                return false;
        }
        return true;
    }

上述代码实测6ms,beats 83.03% of cpp submissions。时间复杂度为O(logn)

3、除了上述方法,我们还有没有其他方法呢?日常逛评论区…

因为2的整数次幂其实在二进制上就是其他位为0,只有一位为1。所以大神又开始处理二进制了,在数学上找关系。

假设n为2的整数次幂,只有一位为1,其他位都为0,那么n&(n-1)必定为0。其他的不满足只有一位为1,其他位为0的条件的数,都不能使得n&(n-1)成立。

为什么?举几个例子:(下面为2进制表示)

1和0,成立。1是2的0次幂。

10和01,成立。2是2的1次幂。

11和10,不成立。

100和011,成立。4是2的2次幂。

101和100,不成立。

110和101,不成立。

111和110,不成立。

1000和0111,成立。8是2的3次幂。

1001和1000,不成立。

1010和1001,不成立。

1011和1010,不成立。

1100和1011,不成立。

1101和1100,不成立。

1110和1101,不成立。

1111和1110,不成立。

观察上述举的这么多的例子,我们可以发现,不成立的都是首位都为1的。首位都为1,那么逐位相与的结果必定不是为0。

而只有2的整数次幂n,以及n-1,两者逐位相与的结果才会为0。

所以我们可以构造出如下代码:

    bool isPowerOfTwo(int n) 
    {
        if(n<=0)
            return false;
        if((n&(n-1))==0)//(n&(n-1))最外层的括号要加上,因为如果n&(n-1)==0,先计算的是等于号
            return true;
        else
            return false;
    }

时间复杂度缩小到O(1),而且二进制处理对于计算机来说更加直接,也更加省时间。

4、还有另一种更加神奇的方法,笔者本人也是第一次见到,十分新颖。

先附上代码:

    bool isPowerOfTwo(int n) 
    {
        if (n>0 && (1073741824 % n == 0))
            return true;
        else
            return false;
    }

大神的这种方法,来源于对int型整数的深刻了解。

int型整数中最大的2的整数次幂是2^30=1073741824,所有的2^k(k为整数)都能被2^30整除。而那些不是2^k的数,比如因子中含有不包括2的素数呀,或者普通的奇数等,都不能被2^30整除,因为2^30只含有30个2的因子。

上述方法十分新颖独特,复杂度也是O(1)。实测时间跟3中的一样。

不过要说最简单最便于计算机处理的方法,还是3中的位操作法。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏wym

hdu1561(数组dp入门)

ACboy很喜欢玩一种战略游戏,在一个地图上,有N座城堡,每座城堡都有一定的宝物,在每次游戏中ACboy允许攻克M个城堡并获得里面的宝物。但由于地理位置原因,有...

1721
来自专栏Bingo的深度学习杂货店

Q121 Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on...

3374
来自专栏云霄雨霁

离散数学中求合取范式&析取范式

4391
来自专栏绿巨人专栏

Modern Algebra 读书笔记

3595
来自专栏逸鹏说道

码农眼中的数学之~数学基础

1维直线、2维平面(长宽)、3维空间(长宽高 | xyz轴)、4维时空(xyz轴+时间轴)

1323
来自专栏章鱼的慢慢技术路

牛课堂算法直播题目

2978
来自专栏数据结构与算法

BZOJ3687: 简单题(dp+bitset)

Description 小呆开始研究集合论了,他提出了关于一个数集四个问题: 1.子集的异或和的算术和。 2.子集的异或和的异或和。 3.子集的算术和的算术和...

3626
来自专栏Grace development

一道看似简单的面试题

这样看似简单的一个面试题, 实际牵出了很多基础知识,本章在为大家补习基础知识的情况下来解答这道题。先亮出答案

732
来自专栏逸鹏说道

码农眼中的数学之~数学基础

写在前面:文章里面的图片公式都是逆天一个个打出来画出来的,公式系列基本上都提供了源码

2117
来自专栏杨建荣的学习笔记

使用贪心算法解决集合覆盖问题

有的同学可能对这些州没概念,这个简称就跟京代表北京,鲁代表山东,甘代表甘肃一样,细细一看,都是西部的一些州。

1352

扫码关注云+社区

领取腾讯云代金券