Addition von Binärzahlen, Gewicht |
| 01.07.2019, 22:46 | Ryan92 | Auf diesen Beitrag antworten » | ||
| Addition von Binärzahlen, Gewicht Ich suche einen möglichst kurzen Beweis für die Tatsache, dass die Summe zweier natürlicher Zahlen in Binärdarstellung maximal so viele 1er enthält wie die beiden Zahlen gemeinsam. Also w(x+y)<= w(x)+w(y). Meine Ideen: Ich dachte an Induktion über die Anzahl an Stellen in der längeren Zahl (die ggf. kürzere würde ich mit führenden Nullen auffüllen). Für n=1 ist alles klar. Man wüsste dann im Induktionsschritt, dass die hinteren n-1 Stellen die Aussage erfüllen. Ich kriege den Beweis durch, muss dann aber immer noch eine Fallunterscheidung machen, je nachdem, ob die hinteren Stellen zu einem Übertrag führen oder nicht, etc. Es erscheint mir einfach alles zu lang und zu aufwendig für so eine triviale Aussage. Kann mir jemand eine einfachere Beweisidee nennen? Danke! |
||||
| 02.07.2019, 07:07 | HAL 9000 | Auf diesen Beitrag antworten » | ||
Ich würde die Induktion eher so organisieren, dass die vorderen (!) (n-1) Stellen die Aussage erfüllen. Einziger interessanter Unterfall hinsichtlich der letzten Stellen beider Zahlen ist dann der Fall "beide 1". In dem Fall würden wir zusätzlich zur Induktionsvoraussetzung die Hilfsaussage brauchen, aber die ist nun nicht so schwer nachzuweisen. |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
