有没有更好的方法来检查数字是否为10的幂?这是我实现的:

    public class PowersOfTen {

    public static boolean isPowerOfTen(long input) {

        if (input % 10 != 0 || input == 0) {
            return false;
        }

        if (input == 10) {
            return true;
        }

        return isPowerOfTen(input/10);
    }

    public static void main(String[] args) {

        System.out.println("1000: " + isPowerOfTen(1000));
        System.out.println("4: " + isPowerOfTen(4));
        System.out.println("0: " + isPowerOfTen(0));
        System.out.println("10: " + isPowerOfTen(10));
        System.out.println("100: " + isPowerOfTen(100));
    }
}


评论

@TomFenech如果输入是整数,则不能为10的负幂。
@ErickWong这是我问的原因之一;我指的是像0.1这样的数字,显然这将需要不同的实现。

@TomFenech打开大量蠕虫。请记住,浮点类型也不能完全代表10的负幂。

1是10的幂,因为10到0的幂是1。此函数为1返回false。

主持人对审​​稿人的注释:是的,有很多不同的方法可以解决此问题。但是,这是“代码审查”,答案必须与问题中的代码有关。如果您提出一个独立的解决方案,则还需要包括一些理由。

#1 楼

为此,递归似乎很繁重。您可以使用几乎相同的逻辑,但有一个简单的循环: 10的倍数)和10的倍数(因为10的所有幂显然都大于1)。首先以小的微优化形式进行正面检查;然后进行正面检查。短路评估将避免执行不必要的除法运算来计算不需要的模量。

如果两个条件都满足,则将整数除以10,然后重复该过程。对于任何10的幂,该值都将以1终止;如果传递了1本身,则无需执行while循环的主体即可这样做。

评论


\ $ \ begingroup \ $
使它变为while(输入> 9 ...可以避免对输入1到9(以及它们的10 ^ x倍数)进行一些多余的额外计算。
\ $ \ endgroup \ $
–杰夫Y
16年1月20日在17:33



\ $ \ begingroup \ $
@JeffY如何处理10的负幂?对于0.1或0.01等输入
\ $ \ endgroup \ $
– Paras
16年1月20日在18:31

\ $ \ begingroup \ $
参见:长输入。
\ $ \ endgroup \ $
–杰夫Y
16年1月20日在19:42

\ $ \ begingroup \ $
@ParasDPain输入为long,这是整数类型。分数值是不可能的。
\ $ \ endgroup \ $
–马克·里德(Mark Reed)
16年1月20日在19:44



\ $ \ begingroup \ $
我明白了,要求。
\ $ \ endgroup \ $
– Paras
16年1月20日在19:47

#2 楼

您也可以只列出它们,因为long数据类型的范围并不多。

OP中代码的优点是简单,清晰和正确。

缺点是有些人可能认为它很冗长。此外,(潜在的)微优化可能是将比较分为多个较小的组,并在通过非幂10的情况下执行二进制搜索以减少比较的次数。

public static boolean isPowerOfTen(long input) {
  return 
    input == 1L
  || input == 10L
  || input == 100L
  || input == 1000L
  || input == 10000L
  || input == 100000L
  || input == 1000000L
  || input == 10000000L
  || input == 100000000L
  || input == 1000000000L
  || input == 10000000000L
  || input == 100000000000L
  || input == 1000000000000L
  || input == 10000000000000L
  || input == 100000000000000L
  || input == 1000000000000000L
  || input == 10000000000000000L
  || input == 100000000000000000L
  || input == 1000000000000000000L;
}   


评论


\ $ \ begingroup \ $
的确如此,或者将它们放在静态(或简洁的环境中)中,以测试其成员资格。
\ $ \ endgroup \ $
– Erick Wong
16年1月19日在19:27

\ $ \ begingroup \ $
排序帽子版本。
\ $ \ endgroup \ $
–疯狂
16年1月20日在10:33

\ $ \ begingroup \ $
也有点慢,因为所有ors将使CPU必须多次分支,但是..无论如何,这都是Java,所以无论如何它都会很慢。
\ $ \ endgroup \ $
–宏线程
16年1月21日在4:36



\ $ \ begingroup \ $
@FilipHaglund-是的。它是否需要帮助还是要进行测试-即使它确实有所帮助,除非这是代码中的关键路径,清晰度的损失也可能无法弥补。
\ $ \ endgroup \ $
–马丁·史密斯
16年1月21日在9:38

\ $ \ begingroup \ $
此答案是此代码高尔夫球问题的基础
\ $ \ endgroup \ $
–已删除
16-2-3在12:44



#3 楼

我认为您的代码不正确,因为我希望isPowerOfTen(1)true

评论


\ $ \ begingroup \ $
你说得对,很好接。
\ $ \ endgroup \ $
– jcm
16年1月19日在6:14

\ $ \ begingroup \ $
只需将if(input == 10)更改为if(input == 1),然后将if放在第一位。
\ $ \ endgroup \ $
–有资格
16年1月19日在8:25

\ $ \ begingroup \ $
因此,“是否有更好的方法来检查数字是否为10的幂?”
\ $ \ endgroup \ $
–马丁·史密斯
16年1月20日在22:58

\ $ \ begingroup \ $
@MartinSmith这不仅仅是简单地重写解决方案并说“你走了”,这更是一个有效的回顾点。
\ $ \ endgroup \ $
– Quill
16年1月20日在23:04

#4 楼

数学替代方法

Math.log10():我已经更新了上面的答案,以处理1e14以上的值,这似乎会失去精度。
单元测试转换为单元测试的形式例如,使用TestNG:

public static boolean isPowerOfTen(long value) {
    // updated answer - check for precision in if statement
    if (value >= 1e14) {
        try {
            return isPowerOfTen(BigDecimal.valueOf(value)
                                    .divide(BigDecimal.valueOf(1e14)).longValueExact());
        } catch (ArithmeticException e) {
            return false;
        }
    }
    double power = Math.log10(value);
    return Double.isFinite(power) && Math.round(power) == power;
}


评论


\ $ \ begingroup \ $
您是否针对精度问题对此进行了测试? 10 ^ 18 + 1的log10将非常接近18,可能比以双精度忠实表示的结果更接近。
\ $ \ endgroup \ $
– Erick Wong
16年1月19日,下午6:51

\ $ \ begingroup \ $
@ErickWong完全有效。 :)更新了我的答案。
\ $ \ endgroup \ $
– h.j.k.
16年1月19日在7:26

\ $ \ begingroup \ $
我不喜欢这种解决方案,因为1)确保自己正确是太难了。浮点数舍入很棘手。 2)使用异常作为核心逻辑的一部分。
\ $ \ endgroup \ $
– CodesInChaos
16年1月19日在14:52

\ $ \ begingroup \ $
@CodesInChaos我个人认为,我的方法的主要问题始于if(值> = 14)。如果可以挥之不去,我认为原始方法是可以的。因此,“注意精度”强调...;)
\ $ \ endgroup \ $
– h.j.k.
16年1月19日在15:40

\ $ \ begingroup \ $
@ h.j.k。您想移开的部分对于方法的正确性至关重要。从根本上讲,问题在于根除像log10这样的函数,其正确性仅近似于需要精确性的问题。
\ $ \ endgroup \ $
– Erick Wong
16年1月19日在19:14



#5 楼

按照马丁·史密斯(Martin Smith)的回答,可以将所有10的幂次存储在一个数组中,然后进行二进制搜索:对于这种小型数据集,效率远不如Martin的效率(在我的计算机上慢2.5倍),但对大型数据集的伸缩性要好得多。

另一方面,如果您需要极高的速度,则可以基于5gon12eder的注释的算法可能值得使用。它会打开输入的低位(您不能长时间打开),如果遇到击中,它将执行线性搜索。在前十亿个正整数上进行计算:


线性搜索(马丁史密斯):2970毫秒
二进制搜索:6908毫秒
打开哈希然后进行线性搜索:1519毫秒


评论


\ $ \ begingroup \ $
我认为switch语句将是这里最快(最易读?)的解决方案。
\ $ \ endgroup \ $
– 5gon12eder
16年1月20日在19:50

\ $ \ begingroup \ $
@ 5gon12eder Java不支持启用多头。
\ $ \ endgroup \ $
–恢复莫妮卡
16年1月20日在19:54

\ $ \ begingroup \ $
Ups,我忘记了……您可以将long的位“散列”为一个int并将其切换为int,但这并不那么明显。
\ $ \ endgroup \ $
– 5gon12eder
16 Jan 20 '20:00



\ $ \ begingroup \ $
@ 5gon12eder如果您进行哈希处理,则会得到误报。您可以哈希,然后如果匹配,则运行精确算法。那会更快,我将相应地更新此答案。
\ $ \ endgroup \ $
–恢复莫妮卡
16年1月20日在21:00

\ $ \ begingroup \ $
@Supuhstar几乎可以肯定,这比二进制搜索或切换要慢,直到表变得很大为止。
\ $ \ endgroup \ $
–恢复莫妮卡
17年4月9日在18:14

#6 楼

迭代版本

此建议类似于@ 200_success的答案。如果您喜欢这种事情,可以将其压缩为for循环:)。兴趣点:


没有递归。递归可以生成精美的代码,但与迭代函数相比,那些额外的函数调用有时会带来明显的性能损失。
使用乘法而不是除法(应该更快,但我对此没有权限) />无需特殊处理0、1或负的input数字。但是需要检查基础。
可以使用除10以外的其他基础。
因为有时Long不够长:)

public static boolean isPowerOf(long input, long base) {
    if (base < 2) throw new IllegalArgumentException("base must be 2 or larger");
    //find the biggest number that is safe to multiply base with without getting integer oveflow
    long safeMultiplier = Long.MAX_VALUE / base;
    long x = 1;
    while (x < input && x <= safeMultiplier) {
        x *= base;
    }
    return x == input;
}


递归版本

递归版本仍使用乘法而不是除法。将递归调用放在函数的最后(就像您也这样做),是对可以执行尾部调用优化的语言的致敬(http://c2.com/cgi/wiki? Wiki / Tail_call)。我不认为Java会这样做。

public static boolean isPowerOf(BigInteger input, BigInteger base) {
    if (base.compareTo(BigInteger.ONE) != 1) {
        throw new IllegalArgumentException("base must be 2 or larger");
    }
    BigInteger x = BigInteger.ONE;
    int comparison;
    while ((comparison = x.compareTo(input)) == -1) {
        x = x.multiply(base);
    }
    return comparison == 0;
}


编辑:


根据@ErickWong的建议
添加了有效基数检查(> 1)
添加了BigInteger版本
修复了错误的溢出检查


评论


\ $ \ begingroup \ $
如果输入相对于MAX_INT / base太大,则迭代版本将陷入无限循环。您是否在大约MAX_INT的2/3倍的输入上对此进行了测试?
\ $ \ endgroup \ $
– Erick Wong
16年1月19日在19:22

\ $ \ begingroup \ $
@ErickWong Wong你是正确的。由于Java似乎在整数溢出上默默地回绕,它将进入无限循环。接得好。我添加了溢出检查。我喜欢我对代码审查帖子的回答刚刚得到审查。 :)
\ $ \ endgroup \ $
–最大
16 Jan 20'8:51



\ $ \ begingroup \ $
不幸的是,溢出检查还不够。当base == 2时很好,但是对于较大的base,完全有可能10 * x溢出到正值。一种检查溢出的更安全方法是在for循环外花费一个除法来找到可以乘以base的最大值。
\ $ \ endgroup \ $
– Erick Wong
16年1月20日在18:30

#7 楼

没有除法,没有模,没有递归?我们开始:

public static boolean power10(int n) {
    int max_power10 = 100000; //whatever you can accept given your type
    int i = 1;
    while ( i != n && i != max_power10) i *= 10;   
    return i == n;
}



改进:

public static boolean power10(int n) {
    int max_power10 = 100000; //whatever you can accept given your type
    if (n > max_power10 ) return false;
    int i = 1;
    while (i < n) i *= 10;   
    return i == n;
}


评论


\ $ \ begingroup \ $
为什么不那么简单(i \ $ \ endgroup \ $
– FranMowinckel
16年3月3日在22:06

\ $ \ begingroup \ $
@FranMowinckel,因为它可能导致溢出。考虑一下n是最大int值的情况。
\ $ \ endgroup \ $
– DarioP
16年4月4日在7:45

\ $ \ begingroup \ $
来吧,这只是一个极限情况,您可以在之前检查(即(n> max_power10)是否返回false)
\ $ \ endgroup \ $
– FranMowinckel
16-2-4在8:31



#8 楼

IMO会更干净,因为:

public static boolean isPowerOfTen(long input) {
    if (input <= 0 ) {
        // powers of 10 can't be 0 or negative
        return false;
    }

    // don't have to worry about negative powers since long input
    // doesn't hold fractions
    for (int pow = 0; pow <= Math.log10(Long.MAX_VALUE); ++pow) {
        if (input == (long)Math.pow(10, pow)) {
            return true;
        }
    }
    return false;
}


Math.log10(Long.MAX_VALUE)将产生最大10的幂,该幂将适合较长的地板,是(被隐式转换为截断)18。 Java没有Math.logb方法,但请回想一下:logb(x)= logc(x)/ logc(b)。因此logb(Long.MAX_VALUE)= Math.log(Long.MAX_VALUE)/ Math.log(b):

public static boolean isPowerOf(long input, int base) {
    if (input <= 0 ) {
        return false;
    }

    for (int pow = 0; pow <= Math.log(Long.MAX_VALUE) / Math.log(base); ++pow) {
        if (input == Math.floor(Math.pow(base, pow))) {
            return true;
        }
    }
    return false;
}


但是我们也可以使用小数学可以直接找到幂并检查它是否是整数:

public static boolean isPowerOf(long input, int base) {
    if (input == 0) {
        return false;
    }

    // use Math.abs since if the argument is NaN or less than zero to Math.log, 
    // then the result is NaN. This makes it work for negative inputs and bases
    Double power = Math.log(Math.abs(input)) / Math.log(Math.abs(base));

    // power might have lost precision, so I'm trying floor and ceiling. These are integers so if either yields the input, return true
    return (input == (long)Math.pow(base, Math.floor(power)) ||
            input == (long)Math.pow(base,  Math.ceil(power)));
}


评论


\ $ \ begingroup \ $
1)对于整数问题,我会避免使用浮点数,这会使进行推理变得非常困难。即使碰巧是正确的,也需要太多的思考才能确保它是正确的。 2)您的代码显然是错误的,因为Math.pow返回一个不能代表所有有效long的双精度型。
\ $ \ endgroup \ $
– CodesInChaos
16年1月19日在14:25

\ $ \ begingroup \ $
3)您可以使用BigInteger.pow代替math.pow。 4)将幂四舍五入为整数将比测试floor和ceil更简单。
\ $ \ endgroup \ $
– CodesInChaos
16 Jan 19 '14:53



#9 楼

这很有趣,但是这个非常基本的解决方案呢?:

String.valueOf(x).matches("^10*$")


它对于使用longBigDecimaltoPlainString()也应适用。

顺便说一句,我知道这不是很高的性能:P。

出于好奇,二进制表示法中的10的幂都以其自身结尾:

1 -> b'1'
10 -> b'x10'
100 -> b'x100'
1000 -> b'x1000'
...

(其中x是'1'和'0'的序列)

评论


\ $ \ begingroup \ $
@WashingtonGuedes对我感到羞耻!谢谢!多么愚蠢的错误
\ $ \ endgroup \ $
– FranMowinckel
16-2-3在11:11

\ $ \ begingroup \ $
无论如何+1 ..我也不必三思而后行...我个人想推断正则表达式的目的
\ $ \ endgroup \ $
–已删除
16-2-3在11:14



#10 楼

迭代比递归更有效。

input == 1也应算作10的幂。

public static boolean isPowerOfTen(long input) {
    while (input > 1) {
        if (input % 10 != 0)
            return false;
        input = input / 10;
    }

    if (input == 1) {
        return true;
    }

    return false;
}


甚至更短的版本(由Landei建议) –谢谢!):

public static boolean isPowerOfTen(long input) {
    while (input > 1) {
        if (input % 10 != 0)
            return false;
        input /= 10;
    }

    return input == 1;
}


评论


\ $ \ begingroup \ $
当我看到这样的代码时,我总是感到困惑。为什么要最后一个?为什么不简单地返回输入== 1?
\ $ \ endgroup \ $
–兰台
16年1月19日在15:07

\ $ \ begingroup \ $
@Landei好吧,我也是。但是我在这里看到过如此多次的代码,以至于我开始相信这是Java程序员社区中的首选样式。现在已更正。
\ $ \ endgroup \ $
–CiaPan
16年1月19日在21:18

\ $ \ begingroup \ $
@Landei,其意图更加明确
\ $ \ endgroup \ $
– Ben Leggiero
17年4月9日在19:13

\ $ \ begingroup \ $
@Supuhstar您的大脑需要处理四行而不是一条,存在分支,并且该方法具有两个出口点而不是一个。这可能是“更明确的”,但显然难以理解。
\ $ \ endgroup \ $
–兰台
17年4月10日在7:56

\ $ \ begingroup \ $
@Landei的四行更简单,用英语更自然地阅读,而不是一条简洁的行在数学上更易读。无论如何,这不是这个地方。如果您想继续进行讨论,请随时通过Supuhstar0@gmail.com给我发送电子邮件。
\ $ \ endgroup \ $
– Ben Leggiero
17-4-10在10:17



#11 楼

如果我们要避免CPU分支,这是一个解决方案,这对于具有广泛指令流水线的CPU的C或C ++等编译语言来说将是不错的选择。它计算所有非零和以10为底的整数。

想法是:当且仅当不存在大于1且正好为1的整数时,我们才有10的幂。 br />
int ispow10(int aInput){
  int lCntO = 0, lCnt1 = 0, lTmp = 0, i = 0;
  for( i=0 ;i < 10; i++, aInput /= 10 ){
    lTmp = aInput % 10;
    lCntO += (lTmp > 1);
    lCnt1 += (lTmp == 1);
  }
return (lCntO == 0)&(lCnt1==1);
}


#12 楼

我知道这可能不是最好的选择,但是我总是从人的角度解决数学上的简单问题,而且还没有人建议在这种情况下研究数字的写法:

boolean isPowerOfTen(int n) {
    char[] digits = (n+"").toCharArray();
    if (digits[0] != '1') return false;
    for (int i = 1; i<digits.length; i++) {
      if (digits[i] != '0') return false;
    }
    return true;
}


您可以轻松地将其扩展为负数(0.000001),并且尽管性能较差,但可以说它比其他方法更易读和易用。