gerzen.net

Knobelaufgabe für Informatiker: es gibt einen Zahlenfeld mit n Zahlen. Alle Zahlen bis auf eine sind in diesem Feld doppelt vorhanden. Es soll ein Algorithmus geschrieben werden, der die einzeln vorhanden Zahl in der linearen Zeit findet. Die Lösung gleich unten ist nicht richtig, auch wenn es funktioniert (php):

$arrZ =array (4,2,1,1,3,2,3);
		$found = false;
		for ($i = 0; $i<=count($arrZ)-1; $i++) {
			for ($j = 0; $j<=count($arrZ)-1; $j++) {
				$isDouble = false;
				if ($j != $i && $arrZ[$j] == $arrZ[$i]){
					$isDouble = true;
					break;
				}
				if ($j == count($arrZ)-1 && $isDouble == false){
					echo "SINGLE: $arrZ[$i]";
					$found = true;
				}
			}
			if ($found == true) break;
		}

Das ist die richtige Lösung, den hier wird die gesuchte Zahl mit nur einer Schleife gefunden:

$arrZ =array (4,2,1,1,3,2,3);
$r = 0; for ($i = 0; $i<=count($arrZ)-1; $i++) {
   $r = $r^$arrZ[$i];
}
echo $r;

Mancher wird sich fragen, warum diese Lösung funktioniert.
Dafür ist der XOR-Operator verantwortlich (in PHP durch “^” vertreten ). Dieser Operator geht zwei übegebene Argumente bitweise durch und vergleicht die einzelnen Bits miteinander. Haben die beiden Bits den gleichen Wert (oder anders ausgedrückt, das Ergebnis der Addition beider Zahlen ist eine gerade Zahl), werden diese Bits auf 0 gesetzt, haben die ungleichen (Additionsergebnis ist ungerade) werden die Bits auf 1 gesetzt.
Zum Beispiel man übergibt an