# Summe der Ziffern einer Zahl EFFIZIENT berechnen?



## Guest (6. Nov 2008)

Hi,

Java bietet im Gegensatz zu anderen Sprachen ja keinen Zugriff auf die Ziffern eines Integers. 
Das Umwandeln in String kostet IMHO aber sehr viel Zeit.

Hier ein Demo Programm:

```
public class Demo {
	public static void main(String[] args) {
		new Demo().run();
	}
	
	public void run(){
		long start = System.currentTimeMillis();
		
		for(int i=1;i<20000000;i++){
			getSum(i);
		}		
		System.out.println((System.currentTimeMillis()-start)/1000+" Sekunden");
	}
	
	
	public int getSum(int zahl){
		int sum = 0;
		String s = String.valueOf(zahl);
		for(int i=0;i<s.length();i++){
			sum = sum + Integer.parseInt(s.substring(i, i+1));
		}
		return sum;
	}
}
```
Das dauert bei mir ca. 15 Sekunden.

Kann man das anders machen und geht das schneller?


----------



## SlaterB (6. Nov 2008)

du kannst aus dem String die Zeichen mit charAt() rausholen,
dann noch minus '0' und nach int umwandeln oder direkt mit dem char rechnen,

schonmal schneller als das parseInt()

---------

wenn du direkt mit der Zahl rechnen willst, dann verwende % 10 und / 10, um per Rechnung an die einzelnen Ziffern zu kommen


----------



## Guest (6. Nov 2008)

Ok,

das bringt schon mal einiges:

```
public class Demo {
	public static void main(String[] args) {
		new Demo().run();
	}
	
	public void run(){
		long start = System.currentTimeMillis();

		
		for(int i=1;i<20000000;i++){
			getSum(i);
		}		
		System.out.println((System.currentTimeMillis()-start)/1000+" Sekunden"); 
	}
	
	
	public int getSum(int zahl){
		int sum = 0;
		String s = String.valueOf(zahl);
		for(int i=0;i<s.length();i++){
			sum = sum + s.charAt(i)-48;
		}
		return sum;
	}
}
```

Das dauert nur noch ca. 3 Sekunden. Gehts noch schneller?


----------



## Wildcard (6. Nov 2008)

Wie Slater sagt mit % und /


----------



## SlaterB (6. Nov 2008)

ist allerdings bisschen langsamer, bei mir recht genau 6 Sekunden

gehts eigentlich um die reine Zählleistung oder reicht dir auch ne Formel?

max * 17/ x2 = fertig

-------


eine Zwischenlösung wäre wohl, statt jedes mal einen neuen String zu erzeugen, ein char-Array anzulegen und da nur die passenden chars auszutauschen,

['0','0','3']

->

['0','0','4']

-> 
['0','0','5']



der Übergang zur Formelrechnung ist dann langsam fließend


----------



## Marco13 (6. Nov 2008)

http://www.java-forum.org/de/viewtopic.php?t=73031&highlight=quersumme


----------



## Gast (6. Nov 2008)

WOW, nicht schlecht Marco13! 1719ms


----------



## Ariol (6. Nov 2008)

```
public int getSum(int zahl){
      int sum = 0;
      for(;zahl > 0; zahl/=10)
      {
    	  sum += zahl%10;
      }
      return sum;
   }
```


----------



## musiKk (6. Nov 2008)

Mal aus Neugier: Welche Sprachen bieten denn einfachen Zugriff auf die Ziffern eines Integer?


----------



## Marco13 (6. Nov 2008)

Vermutlich COBOL mit http://de.wikipedia.org/wiki/BCD-Code :lol:


----------



## Gast (6. Nov 2008)

php


----------



## maki (6. Nov 2008)

Gast hat gesagt.:
			
		

> php


Ob das wohl schneller arbeitet als Marcos Variante?


----------



## Landei (7. Nov 2008)

```
public class Quersumme {

  private final static int[] SUM = new int[] {
      0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
      1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
      2, 3, 4, 5, 6, 7, 8, 9, 10, 11,
      3, 4, 5, 6, 7, 8, 9, 10, 11, 12,
      4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
      5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
      6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
      7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
      8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
      9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
      1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
      2, 3, 4, 5, 6, 7, 8, 9, 10, 11,
      3, 4, 5, 6, 7, 8, 9, 10, 11, 12,
      4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
      5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
      6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
      7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
      8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
      9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
      10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
      2, 3, 4, 5, 6, 7, 8, 9, 10, 11,
      3, 4, 5, 6, 7, 8, 9, 10, 11, 12,
      4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
      5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
      6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
      7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
      8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
      9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
      10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
      11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
      3, 4, 5, 6, 7, 8, 9, 10, 11, 12,
      4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
      5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
      6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
      7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
      8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
      9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
      10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
      11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
      12, 13, 14, 15, 16, 17, 18, 19, 20, 21,
      4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
      5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
      6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
      7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
      8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
      9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
      10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
      11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
      12, 13, 14, 15, 16, 17, 18, 19, 20, 21,
      13, 14, 15, 16, 17, 18, 19, 20, 21, 22,
      5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
      6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
      7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
      8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
      9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
      10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
      11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
      12, 13, 14, 15, 16, 17, 18, 19, 20, 21,
      13, 14, 15, 16, 17, 18, 19, 20, 21, 22,
      14, 15, 16, 17, 18, 19, 20, 21, 22, 23,
      6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
      7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
      8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
      9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
      10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
      11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
      12, 13, 14, 15, 16, 17, 18, 19, 20, 21,
      13, 14, 15, 16, 17, 18, 19, 20, 21, 22,
      14, 15, 16, 17, 18, 19, 20, 21, 22, 23,
      15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
      7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
      8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
      9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
      10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
      11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
      12, 13, 14, 15, 16, 17, 18, 19, 20, 21,
      13, 14, 15, 16, 17, 18, 19, 20, 21, 22,
      14, 15, 16, 17, 18, 19, 20, 21, 22, 23,
      15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
      16, 17, 18, 19, 20, 21, 22, 23, 24, 25,
      8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
      9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
      10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
      11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
      12, 13, 14, 15, 16, 17, 18, 19, 20, 21,
      13, 14, 15, 16, 17, 18, 19, 20, 21, 22,
      14, 15, 16, 17, 18, 19, 20, 21, 22, 23,
      15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
      16, 17, 18, 19, 20, 21, 22, 23, 24, 25,
      17, 18, 19, 20, 21, 22, 23, 24, 25, 26,
      9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
      10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
      11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
      12, 13, 14, 15, 16, 17, 18, 19, 20, 21,
      13, 14, 15, 16, 17, 18, 19, 20, 21, 22,
      14, 15, 16, 17, 18, 19, 20, 21, 22, 23,
      15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
      16, 17, 18, 19, 20, 21, 22, 23, 24, 25,
      17, 18, 19, 20, 21, 22, 23, 24, 25, 26,
      18, 19, 20, 21, 22, 23, 24, 25, 26, 27
  };

  public static int quersumme(int zahl) {
    int sum = 0;
    while (zahl > 0) {
      sum += SUM[zahl % 1000];
      zahl /= 1000;
    }
    return sum;
  }

  public static void main(String ...args) {
    System.out.println(quersumme(1234567));
  }
}
```


----------



## SlaterB (7. Nov 2008)

ob wohl ein switch schneller ist als ein Array-Zugriff?
bitte ausprobieren 

das müsste man tatsächlich programmieren, das Array hätte man auch dynamisch füllen lassen können
 (ok, den Quellcode für das switch kann auch ein Programm schreiben)


----------



## Landei (7. Nov 2008)

Eine andere Idee wäre, die letzte Ziffer ohne % zu ermitteln:

```
private static int lastDigit(int zahl) {
     int hex = zahl & 0xF;
     switch(hex) {
     case 10 : return 0;
     case 11 : return 1;
     case 12 : return 2;
     case 13 : return 3;
     case 14 : return 4;
     case 15 : return 5;
     default: return hex;
     }
 }
```


----------



## tfa (7. Nov 2008)

Das wär aber eine schlechte Idee.

lastDigit(16)==0?


----------



## Der Müde Joe (7. Nov 2008)

>Eine andere Idee wäre, die letzte Ziffer ohne % zu ermitteln: 


```
int sum = 0;
		int temp;
		while (zahl > 0) {
			temp = zahl / 10; //div 10
			sum += (zahl - (temp << 3) - (temp << 1)); //orig - (temp * 10)
			zahl = temp;
		}
```

recht schnell..auf der idee von Marco13 bzw aus Long (hingegen ohne Tabelle)


----------



## Landei (7. Nov 2008)

Hab auch gerade gemerkt, dass mein Code nicht ging...

Aber man könnte beides kombinieren... Also so eine Formel für %1000, und dann in meinem Array nachgucken.


----------



## Landei (7. Nov 2008)

Funktioniert:

```
public static int quersumme(int zahl) {
    int sum = 0;
    while (zahl > 0) {
      int temp = zahl / 1000;
      sum += SUM[zahl - (temp << 10) + (temp << 4) + (temp << 3)];
      zahl = temp;
    }
    return sum;
  }
```


----------

