Java 获取int中位数的方法？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1306727/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Way to get number of digits in an int?
提问by fnst
Is there a neater way for getting the length of an int than this method?
有没有比这种方法更简洁的方法来获取 int 的长度？
int length = String.valueOf(1000).length();
采纳答案by Michael Borgwardt
Your String-based solution is perfectly OK, there is nothing "un-neat" about it. You have to realize that mathematically, numbers don't have a length, nor do they have digits. Length and digits are both properties of a physical representationof a number in a specific base, i.e. a String.
您的基于字符串的解决方案完全可以，没有什么“不整洁”的地方。你必须意识到，从数学上讲，数字没有长度，也没有数字。长度和数字都是特定基数（即字符串）中数字的物理表示的属性。
A logarithm-based solution does (some of) the same things the String-based one does internally, and probably does so (insignificantly) faster because it only produces the length and ignores the digits. But I wouldn't actually consider it clearer in intent - and that's the most important factor.
基于对数的解决方案执行（某些）与基于字符串的解决方案在内部所做的相同的事情，并且可能（微不足道）更快地执行此操作，因为它只产生长度而忽略数字。但我实际上不会认为它的意图更清晰——这是最重要的因素。
回答by Dmitry Brant
The logarithm is your friend:
对数是你的朋友：
int n = 1000;
int length = (int)(Math.log10(n)+1);
NB: only valid for n > 0.
注意：仅对 n > 0 有效。
回答by Dirk
Since the number of digits in base 10 of an integer is just 1 + truncate(log10(number)), you can do:
由于整数的基数为 10 的位数仅为1 + truncate(log10(number))，因此您可以执行以下操作：
public class Test {
public static void main(String[] args) {
final int number = 1234;
final int digits = 1 + (int)Math.floor(Math.log10(number));
System.out.println(digits);
}
}
Editedbecause my last edit fixed the code example, but not the description.
编辑是因为我上次编辑修复了代码示例，而不是描述。
回答by DmitryK
Can I try? ;)
我可以试试吗？;)
based on Dirk's solution
基于德克的解决方案
final int digits = number==0?1:(1 + (int)Math.floor(Math.log10(Math.abs(number))));
回答by Jean
Curious, I tried to benchmark it ...
好奇，我试图对它进行基准测试......
import org.junit.Test;
import static org.junit.Assert.*;
public class TestStack1306727 {
@Test
public void bench(){
int number=1000;
int a= String.valueOf(number).length();
int b= 1 + (int)Math.floor(Math.log10(number));
assertEquals(a,b);
int i=0;
int s=0;
long startTime = System.currentTimeMillis();
for(i=0, s=0; i< 100000000; i++){
a= String.valueOf(number).length();
s+=a;
}
long stopTime = System.currentTimeMillis();
long runTime = stopTime - startTime;
System.out.println("Run time 1: " + runTime);
System.out.println("s: "+s);
startTime = System.currentTimeMillis();
for(i=0,s=0; i< 100000000; i++){
b= number==0?1:(1 + (int)Math.floor(Math.log10(Math.abs(number))));
s+=b;
}
stopTime = System.currentTimeMillis();
runTime = stopTime - startTime;
System.out.println("Run time 2: " + runTime);
System.out.println("s: "+s);
assertEquals(a,b);
}
}
the results are :
结果是：
Run time 1: 6765 s: 400000000 Run time 2: 6000 s: 400000000
Now I am left to wonder if my benchmark actually means something but I do get consistent results (variations within a ms) over multiple runs of the benchmark itself ... :) It looks like it's useless to try and optimize this...
现在我想知道我的基准测试是否真的意味着什么，但我确实在基准测试本身的多次运行中得到了一致的结果（毫秒内的变化）...... :) 看起来尝试优化这个是没有用的......
edit: following ptomli's comment, I replaced 'number' by 'i' in the code above and got the following results over 5 runs of the bench :
编辑：根据 ptomli 的评论，我将上面代码中的“数字”替换为“i”，并在 5 次试验中得到以下结果：
Run time 1: 11500 s: 788888890 Run time 2: 8547 s: 788888890 Run time 1: 11485 s: 788888890 Run time 2: 8547 s: 788888890 Run time 1: 11469 s: 788888890 Run time 2: 8547 s: 788888890 Run time 1: 11500 s: 788888890 Run time 2: 8547 s: 788888890 Run time 1: 11484 s: 788888890 Run time 2: 8547 s: 788888890
回答by Jay
Two comments on your benchmark: Java is a complex environment, what with just-in-time compiling and garbage collection and so forth, so to get a fair comparison, whenever I run a benchmark, I always: (a) enclose the two tests in a loop that runs them in sequence 5 or 10 times. Quite often the runtime on the second pass through the loop is quite different from the first. And (b) After each "approach", I do a System.gc() to try to trigger a garbage collection. Otherwise, the first approach might generate a bunch of objects, but not quite enough to force a garbage collection, then the second approach creates a few objects, the heap is exhausted, and garbage collection runs. Then the second approach is "charged" for picking up the garbage left by the first approach. Very unfair!
关于你的基准测试的两条评论：Java 是一个复杂的环境，有即时编译和垃圾收集等等，所以为了公平比较，每当我运行基准测试时，我总是：(a) 附上两个测试在按顺序运行它们 5 或 10 次的循环中。通常，第二次通过循环的运行时间与第一次完全不同。并且 (b) 在每次“方法”之后，我执行 System.gc() 以尝试触发垃圾收集。否则，第一种方法可能会生成一堆对象，但不足以强制进行垃圾收集，然后第二种方法会创建一些对象，堆耗尽，垃圾收集运行。然后第二种方法“收费”用于捡拾第一种方法留下的垃圾。很不公平！
That said, neither of the above made a significant difference in this example.
也就是说，在这个例子中，上述两者都没有产生显着差异。
With or without those modifications, I got very different results than you did. When I ran this, yes, the toString approach gave run times of 6400 to 6600 millis, while the log approach topok 20,000 to 20,400 millis. Instead of being slightly faster, the log approach was 3 times slower for me.
不管有没有这些修改，我得到的结果与你大不相同。当我运行它时，是的，toString 方法的运行时间为 6400 到 6600 毫秒，而日志方法的运行时间为 20,000 到 20,400 毫秒。对我来说，日志方法不是稍微快一点，而是慢了 3 倍。
Note that the two approaches involve very different costs, so this isn't totally shocking: The toString approach will create a lot of temporary objects that have to be cleaned up, while the log approach takes more intense computation. So maybe the difference is that on a machine with less memory, toString requires more garbage collection rounds, while on a machine with a slower processor, the extra computation of log would be more painful.
请注意，这两种方法涉及的成本非常不同，因此这并不完全令人震惊：toString 方法将创建许多必须清理的临时对象，而日志方法需要更密集的计算。所以可能不同的是，在内存较少的机器上，toString 需要更多的垃圾收集轮次，而在处理器较慢的机器上，额外的日志计算会更痛苦。
I also tried a third approach. I wrote this little function:
我还尝试了第三种方法。我写了这个小函数：
static int numlength(int n)
{
if (n == 0) return 1;
int l;
n=Math.abs(n);
for (l=0;n>0;++l)
n/=10;
return l;
}
That ran in 1600 to 1900 millis -- less than 1/3 of the toString approach, and 1/10 the log approach on my machine.
运行时间为 1600 到 1900 毫秒——不到 toString 方法的 1/3，是我机器上日志方法的 1/10。
If you had a broad range of numbers, you could speed it up further by starting out dividing by 1,000 or 1,000,000 to reduce the number of times through the loop. I haven't played with that.
如果您的数字范围很广，您可以通过开始除以 1,000 或 1,000,000 以减少循环次数来进一步加快速度。我没玩过那个。
回答by Marian
The fastest approach: divide and conquer.
最快的方法：分而治之。
Assuming your range is 0 to MAX_INT, then you have 1 to 10 digits. You can approach this interval using divide and conquer, with up to 4 comparisons per each input. First, you divide [1..10] into [1..5] and [6..10] with one comparison, and then each length 5 interval you divide using one comparison into one length 3 and one length 2 interval. The length 2 interval requires one more comparison (total 3 comparisons), the length 3 interval can be divided into length 1 interval (solution) and a length 2 interval. So, you need 3 or 4 comparisons.
假设您的范围是 0 到 MAX_INT，那么您有 1 到 10 位数字。您可以使用分治法来接近此间隔，每个输入最多进行 4 次比较。首先，将 [1..10] 分为 [1..5] 和 [6..10] 进行一次比较，然后将每个长度为 5 的区间使用一次比较分为一个长度为 3 的区间和一个长度为 2 的区间。长度2区间需要再进行一次比较（共3次比较），长度3区间又可以分为长度1区间（解）和长度2区间。因此，您需要进行 3 或 4 次比较。
No divisions, no floating point operations, no expensive logarithms, only integer comparisons.
没有除法，没有浮点运算，没有昂贵的对数，只有整数比较。
Code (long but fast):
代码（长但快）：
if (n < 100000){
// 5 or less
if (n < 100){
// 1 or 2
if (n < 10)
return 1;
else
return 2;
}else{
// 3 or 4 or 5
if (n < 1000)
return 3;
else{
// 4 or 5
if (n < 10000)
return 4;
else
return 5;
}
}
} else {
// 6 or more
if (n < 10000000) {
// 6 or 7
if (n < 1000000)
return 6;
else
return 7;
} else {
// 8 to 10
if (n < 100000000)
return 8;
else {
// 9 or 10
if (n < 1000000000)
return 9;
else
return 10;
}
}
}
Benchmark (after JVM warm-up) - see code below to see how the benchmark was run:
基准测试（在 JVM 预热之后） - 请参阅下面的代码以了解基准测试是如何运行的：
- baseline method (with String.length): 2145ms
- log10 method: 711ms = 3.02 times as fast as baseline
- repeated divide: 2797ms = 0.77 times as fast as baseline
- divide-and-conquer: 74ms = 28.99
times as fast as baseline
- 基线方法（带 String.length）：2145ms
- log10 方法：711ms = 比基线快 3.02 倍
- 重复除法：2797ms = 基线速度的 0.77 倍
- 分而治之：74ms =
比基线快28.99倍
Full code:
完整代码：
public static void main(String[] args)
throws Exception
{
// validate methods:
for (int i = 0; i < 1000; i++)
if (method1(i) != method2(i))
System.out.println(i);
for (int i = 0; i < 1000; i++)
if (method1(i) != method3(i))
System.out.println(i + " " + method1(i) + " " + method3(i));
for (int i = 333; i < 2000000000; i += 1000)
if (method1(i) != method3(i))
System.out.println(i + " " + method1(i) + " " + method3(i));
for (int i = 0; i < 1000; i++)
if (method1(i) != method4(i))
System.out.println(i + " " + method1(i) + " " + method4(i));
for (int i = 333; i < 2000000000; i += 1000)
if (method1(i) != method4(i))
System.out.println(i + " " + method1(i) + " " + method4(i));
// work-up the JVM - make sure everything will be run in hot-spot mode
allMethod1();
allMethod2();
allMethod3();
allMethod4();
// run benchmark
Chronometer c;
c = new Chronometer(true);
allMethod1();
c.stop();
long baseline = c.getValue();
System.out.println(c);
c = new Chronometer(true);
allMethod2();
c.stop();
System.out.println(c + " = " + StringTools.formatDouble((double)baseline / c.getValue() , "0.00") + " times as fast as baseline");
c = new Chronometer(true);
allMethod3();
c.stop();
System.out.println(c + " = " + StringTools.formatDouble((double)baseline / c.getValue() , "0.00") + " times as fast as baseline");
c = new Chronometer(true);
allMethod4();
c.stop();
System.out.println(c + " = " + StringTools.formatDouble((double)baseline / c.getValue() , "0.00") + " times as fast as baseline");
}
private static int method1(int n)
{
return Integer.toString(n).length();
}
private static int method2(int n)
{
if (n == 0)
return 1;
return (int)(Math.log10(n) + 1);
}
private static int method3(int n)
{
if (n == 0)
return 1;
int l;
for (l = 0 ; n > 0 ;++l)
n /= 10;
return l;
}
private static int method4(int n)
{
if (n < 100000)
{
// 5 or less
if (n < 100)
{
// 1 or 2
if (n < 10)
return 1;
else
return 2;
}
else
{
// 3 or 4 or 5
if (n < 1000)
return 3;
else
{
// 4 or 5
if (n < 10000)
return 4;
else
return 5;
}
}
}
else
{
// 6 or more
if (n < 10000000)
{
// 6 or 7
if (n < 1000000)
return 6;
else
return 7;
}
else
{
// 8 to 10
if (n < 100000000)
return 8;
else
{
// 9 or 10
if (n < 1000000000)
return 9;
else
return 10;
}
}
}
}
private static int allMethod1()
{
int x = 0;
for (int i = 0; i < 1000; i++)
x = method1(i);
for (int i = 1000; i < 100000; i += 10)
x = method1(i);
for (int i = 100000; i < 1000000; i += 100)
x = method1(i);
for (int i = 1000000; i < 2000000000; i += 200)
x = method1(i);
return x;
}
private static int allMethod2()
{
int x = 0;
for (int i = 0; i < 1000; i++)
x = method2(i);
for (int i = 1000; i < 100000; i += 10)
x = method2(i);
for (int i = 100000; i < 1000000; i += 100)
x = method2(i);
for (int i = 1000000; i < 2000000000; i += 200)
x = method2(i);
return x;
}
private static int allMethod3()
{
int x = 0;
for (int i = 0; i < 1000; i++)
x = method3(i);
for (int i = 1000; i < 100000; i += 10)
x = method3(i);
for (int i = 100000; i < 1000000; i += 100)
x = method3(i);
for (int i = 1000000; i < 2000000000; i += 200)
x = method3(i);
return x;
}
private static int allMethod4()
{
int x = 0;
for (int i = 0; i < 1000; i++)
x = method4(i);
for (int i = 1000; i < 100000; i += 10)
x = method4(i);
for (int i = 100000; i < 1000000; i += 100)
x = method4(i);
for (int i = 1000000; i < 2000000000; i += 200)
x = method4(i);
return x;
}
Again, benchmark:
再次，基准：
- baseline method (with String.length): 2145ms
- log10 method: 711ms = 3.02 times as fast as baseline
- repeated divide: 2797ms = 0.77 times as fast as baseline
- divide-and-conquer: 74ms = 28.99
times as fast as baseline
- 基线方法（带 String.length）：2145ms
- log10 方法：711ms = 比基线快 3.02 倍
- 重复除法：2797ms = 基线速度的 0.77 倍
- 分而治之：74ms =
比基线快28.99倍
Edit:After I wrote the benchmark, I took a sneak peak into Integer.toString from Java 6, and I found that it uses:
编辑：在我编写了基准测试之后，我从 Java 6 中偷偷进入了 Integer.toString，我发现它使用：
final static int [] sizeTable = { 9, 99, 999, 9999, 99999, 999999, 9999999,
99999999, 999999999, Integer.MAX_VALUE };
// Requires positive x
static int stringSize(int x) {
for (int i=0; ; i++)
if (x <= sizeTable[i])
return i+1;
}
I benchmarked it against my divide-and-conquer solution:
我根据我的分而治之的解决方案对其进行了基准测试：
- divide-and-conquer: 104ms
- Java 6 solution - iterate and compare: 406ms
- 分而治之：104ms
- Java 6 解决方案 - 迭代和比较：406ms
Mine is about 4x as fast as the Java 6 solution.
我的大约是 Java 6 解决方案的 4 倍。
回答by J.A.I.L.
Marian's solution adapted for longtype numbers (up to 9,223,372,036,854,775,807), in case someone want's to Copy&Paste it. In the program I wrote this for numbers up to 10000 were much more probable, so I made a specific branch for them. Anyway it won't make a significative difference.
玛丽安的解决方案适用于长类型数字（最多 9,223,372,036,854,775,807），以防有人想要复制和粘贴它。在我为 10000 以内的数字编写的程序中，它的可能性要大得多，所以我为它们做了一个特定的分支。无论如何，它不会产生显着的差异。
public static int numberOfDigits (long n) {
// Guessing 4 digit numbers will be more probable.
// They are set in the first branch.
if (n < 10000L) { // from 1 to 4
if (n < 100L) { // 1 or 2
if (n < 10L) {
return 1;
} else {
return 2;
}
} else { // 3 or 4
if (n < 1000L) {
return 3;
} else {
return 4;
}
}
} else { // from 5 a 20 (albeit longs can't have more than 18 or 19)
if (n < 1000000000000L) { // from 5 to 12
if (n < 100000000L) { // from 5 to 8
if (n < 1000000L) { // 5 or 6
if (n < 100000L) {
return 5;
} else {
return 6;
}
} else { // 7 u 8
if (n < 10000000L) {
return 7;
} else {
return 8;
}
}
} else { // from 9 to 12
if (n < 10000000000L) { // 9 or 10
if (n < 1000000000L) {
return 9;
} else {
return 10;
}
} else { // 11 or 12
if (n < 100000000000L) {
return 11;
} else {
return 12;
}
}
}
} else { // from 13 to ... (18 or 20)
if (n < 10000000000000000L) { // from 13 to 16
if (n < 100000000000000L) { // 13 or 14
if (n < 10000000000000L) {
return 13;
} else {
return 14;
}
} else { // 15 or 16
if (n < 1000000000000000L) {
return 15;
} else {
return 16;
}
}
} else { // from 17 to ...?20?
if (n < 1000000000000000000L) { // 17 or 18
if (n < 100000000000000000L) {
return 17;
} else {
return 18;
}
} else { // 19? Can it be?
// 10000000000000000000L is'nt a valid long.
return 19;
}
}
}
}
}
回答by Sinista
How about plain old Mathematics? Divide by 10 until you reach 0.
普通的旧数学怎么样？除以 10，直到达到 0。
public static int getSize(long number) {
int count = 0;
while (number > 0) {
count += 1;
number = (number / 10);
}
return count;
}
回答by Jedi Dula
What about this recursive method?
这个递归方法怎么样？
private static int length = 0;
public static int length(int n) {
length++;
if((n / 10) < 10) {
length++;
} else {
length(n / 10);
}
return length;
}
