如何判定一个数是否为2的N次方

最保险的还是位运算
服务器君一共花费了87.924 ms进行了3次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

题目:给定一个整数num,判断这个整数是否是2的N次方。比如,2,4,8是2的那次方,6,10不是2的N次方。

请看下面的程序:

public static bool Check1(int num)
{
    int i = 1;
    while (true)
    {
        if (i > num)
            return false;
        if (i == num)
            return true;
        i = i * 2;
    }
}

不断的循环num%2,如果不等于0,return false,如果等于0,num=num/2,一直做到num=1

public static bool Check2(int num)
{
    if (num == 1)
        return true;
    else
    {
        do
        {
            if (num % 2 == 0)
                num = num / 2;
            else
                return false;
        }
        while (num != 1);
        return true;
    }
}

其实这两种算法的思路都是相同的,但是第二种相对第一种更高效写,因为如果不是2的N次方,可以少循环很多次!

由于2的N次方的数二进制表示是第1位为1,其余为0,而x-1(假如x为2的N次方)得到的数的二进制表示恰恰是第1位为0,其余为1,两者相与,得到的结果就为0,否则结果肯定不为0。

public static boolean getResult(int num) 
{ 
	if (num <= 1) 
    { 
		return false; 
	} 
    else 
    { 
		return ((num & (num - 1)) == 0) ? true : false; 
	} 
} 
public static void main(String[] args) { 
	System.out.println(getResult(32)); 
} 

上面的程序多判断了一个1. 我们知道, 1是2的0次方。 1应该是符合要求的。下面修正:

	public static bool floor_7(int num)
    {
        if (num <= 1)
        {
            return false;
        }
        else
        {
            return ((num & (num - 1)) == 0) ? true : false;
        }
    }

如果一个数是2的整数次幂,那么表示为二进制的时候会是这样:010000....

除了2的零次方,即1之外,这个数减一会得到:001111....

换言之得到一个前面全是0后面全是1的数,把这个数和原数做个按位与,得到:000000.....

换言之,如果一个数n,其不为1,且n-1 & n = 0,那么n就是一个2的整数次幂。因为只要他表达为二进制时存在两个1,就不会满足这条规律。所以最简判断方法就是:

if ( n < 0 )
throw new InvalidOperationException();
if ( n < 2 )
return false;
return n & ( n - 1 ) == 0

修正之后:

	public bool floor_8(int n)
    {
        if (n < 0)
            throw new InvalidOperationException();
        if (n < 2)
            return false;
        return n & (n - 1) == 0;
    }

对数算法:

bool foo(int x)
{
    float ret = log(x)/log(2); 
    return abs((int) ret - ret) <= 0.00001;
}

修正后:

	public bool floor_22(int x)
    {
        float ret = log(x) / log(2);
        return abs((int)ret - ret) <= 0.00001;
    }

对数算法比较有趣, 可惜, 浮点误差毕竟不是个容易避开的问题。因为浮点数不能直接比较, 所以用了一个0.00001来做尺度。这就存在了一个问题:当x很大的时候呢?我找了一个变态的数字来测试:0x10000001

结果是true。因为结果的小数部分实在是太小了。

static void Main(string[] args)
{
	int i = int.Parse(Console.ReadLine());
	Console.WriteLine(IsCheck(i));
}
public static bool IsCheck(int num)
{
	double result = Math.Log(num, 2);
	if (result.ToString().IndexOf(".") >= 0)
	{
		return false;
	}
	else
	{
		return true;
	}
}

相同的问题。 只要使用了LOG, 就无法避免掉浮点数丢精度的问题。 这是没办法的事情。

	public static bool floor_37(int num)
    {
        double result = Math.Log(num, 2);
        if (result.ToString().IndexOf(".") >= 0)
        {
            return false;
        }
        else
        {
            return true;
        }
    }

所以总结了下, (x)&(x-1)的算法还没有被证明, 不知道除了0还有没有别的反例。因为毕竟这个算式没有严密的证明过程。

因此我觉得, 最保险的还是位运算, 看多少个1, 来的最实在。当然这里存在一个负数的问题。第一位是1, 剩下全是0的问题。 不过有一位聪明的回复者提供了一个很强大的方法来避开负数的用例:他给参数定的类型是uint!

好吧你赢了。

本文地址:http://www.nowamagic.net/librarys/veda/detail/1031,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/1031

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《深入理解计算机系统(原书第2版)》 布莱恩特(Randal E.Bryant) (作者), 奥哈拉伦(David R.O'Hallaron) (作者), 龚奕利 (译者), 雷迎春 (译者)

《深入理解计算机系统》从程序员的视角详细阐述计算机系统的本质概念,并展示这些概念如何实实在在地影响应用程序的正确性、性能和实用性。全书共12章,主要内容包括信息的表示和处理、程序的机器级表示、处理器体系结构、优化程序性能、存储器层次结构、链接、异常控制流、虚拟存储器、系统级I/O、网络编程、并发编程等。书中提供子大量的例子和练习题,并给出部分答案,有助于读者加深对正文所述概念和知识的理解。

更多计算机宝库...