---

"The checksum field is the 16 bit one's complement of the one's complement
sum of all 16 bit words in the header"

Hvad er det lige "one's complement" betyder? at man kører en xor, eller...?

---

Desilva wrote:
>
> "The checksum field is the 16 bit one's complement of the one's complement
> sum of all 16 bit words in the header"
>
> Hvad er det lige "one's complement" betyder? at man kører en xor, eller...?

Et komplement er, når du ikke ser på den første bit som fortegnsbit, og
derfor kan repræsentere tal i intervallet fra [0;2^16] i stedet for
[-2^15;2^15-1]

Kort sagt, din checksum indeholder også fortegnsbitten
--
MVH

Mikkel Bjerg

---

Mikkel Bjerg wrote:
>
> Desilva wrote:
> >
> > "The checksum field is the 16 bit one's complement of the one's complement
> > sum of all 16 bit words in the header"
> >
> > Hvad er det lige "one's complement" betyder? at man kører en xor, eller...?
>
> Et komplement er, når du ikke ser på den første bit som fortegnsbit, og
> derfor kan repræsentere tal i intervallet fra [0;2^16] i stedet for
> [-2^15;2^15-1]
>
> Kort sagt, din checksum indeholder også fortegnsbitten

Du kan evt tage et kig på denne note
<URL:http://www.daimi.au.dk/dArkOS/Uge37/Talrep.ps>

--
MVH

Mikkel Bjerg

---

> Et komplement er, når du ikke ser på den første bit som fortegnsbit, og
> derfor kan repræsentere tal i intervallet fra [0;2^16] i stedet for
> [-2^15;2^15-1]

Ok, det var jo simpelt. Det ville jeg nok alligevel have gjort, da jeg ikke
regner med en fortegnsbit med mindre der udtrykkeligt er angivet at en sådan
er til stede.

Tak for hjælpen

---

Scripsit Mikkel Bjerg <mbjerg@daimi.au.dk>

> Et komplement er, når du ikke ser på den første bit som fortegnsbit, og
> derfor kan repræsentere tal i intervallet fra [0;2^16] i stedet for
> [-2^15;2^15-1]

Nej, det er fortegnsløs repræsentation. Et-komplement er et tal
negeres ved at negere hvert af bittene individuelt, så

0111111111111111 = 32767
:
0000000000000000 = 0
1111111111111111 = -0
:
1000000000000000 = -32767

Se fx http://www.ibiblio.org/pub/languages/fortran/ch4-10.html
http://www-ccrma.stanford.edu/~jos/r320/One_s_Complement_Fixed_Poin.html
http://courses.cs.vt.edu/~csonline/NumberSystems/Lessons/OnesComplement/Lesson.html

I en "et-komplement-sum" lægger man menten fra venstre side til i
højre side efter additionen. Det er en primitiv måde at sikre sig at
forskelle i data ikke bare forsvinder ud til venstre for den del af
checksummen man kan se.

Den kunne repræsenteres effektivt på en CISC-maskine som en
serie add-with-carry-operationer, fx i x86-assembler:

   xorw %dx,%dx
   clc
ltop:   lodsw
   adcw %ax,%dx
   loop ltop
   ...

På RISC-maskiner (eller hvis man skal skrive C-source) ville man nok
snarere tælle alle ordene sammen i en 32-bit-sum, og dernæst to gange
lægge de øverste 16 bit sammen med de nederste.

--
Henning Makholm "Uh ... a picture of me with my hair pinned up
in a towel and standing in front of a grid without a
trace of makeup? *Are you out of your rock-happy mind?*"

---

Mikkel Bjerg skrev:

>Et komplement er, når du ikke ser på den første bit som fortegnsbit

Øh ... den var ny.

Man beregner 1's komplement ved at skifte alle bittene til den
modsatte værdi. Eksempel: 01011010 -> 10100101 osv.

Det er den metode til at angive negative tal der virker mest
intuitiv. Men eftersom det resulterer i to forskellige værdier
for 0, er der nogen der foretrækker at bruge 2's komplement hvor
man lige adderer 1 til 1's komplement (og glemmer en evt.
slutmente). Det foresvæver dog mig at der findes systemer hvor
man ikke er bange for -0, men 2's komplement er det mest brugte.
Tanenbaum kalder 1's komplement for "obsolete" (forældet), men
jeg mener også at huske en artikel hvor netop kun 1's komplement
gav de rigtige resultater (man kunne skelne mellem om et
0-resultat var nået fra minussiden eller plussiden).

Ved både 1's og 2's komplement er den mest betydende bit
fortegnsbit.

--
Bertel
http://lundhansen.dk/bertel/   FIDUSO: http://fiduso.dk/

---

Bertel Lund Hansen wrote:
>
> Mikkel Bjerg skrev:
>
> >Et komplement er, når du ikke ser på den første bit som fortegnsbit
>
> Øh ... den var ny.
>
> Man beregner 1's komplement ved at skifte alle bittene til den
> modsatte værdi. Eksempel: 01011010 -> 10100101 osv.
>
> Det er den metode til at angive negative tal der virker mest
> intuitiv. Men eftersom det resulterer i to forskellige værdier
> for 0, er der nogen der foretrækker at bruge 2's komplement hvor
> man lige adderer 1 til 1's komplement (og glemmer en evt.
> slutmente).

Øhm, jeg synes da at den sidste metode er mere intuitiv.

Nu regner jeg lige decimalt i stedet for binært (for tydelighed).
Hvad sker der hvis man prøver at udregne differensen 356-429 med den
sædvanlige algoritme (starte med enere, så tiere, hundredere etc.):

356
- 429
________ (læses fra højre mod venstre)
....99927

Det er altså naturligt at repræsentere resultatet ("minus treoghalv-
fjerds") som ...99927. Thi se selv, når man lægger ...00073 til, så
får man jo nul.

Denne metode svarer til det der sker på en tæller på en båndoptager
hvis man spoler baglæns forbi "000".

Mener du at man burde repræsentere "minus treoghalvfjerds" som
....99926?
(I øvrigt må "skifte bit" (binære tal) svare til at "trække
cifferet fra 9" (for decimale tal).)

--
Jeppe Stig Nielsen <URL:http://jeppesn.dk/>. «

"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)

---

Nå ja, her er en oversigt:

"alm. tal" nierkomplement tierkomplement
___________________________________________
-4 9995 9996
-3 9996 9997
-2 9997 9998
-1 9998 9999
0 9999 og 0000 0000
1 0001 0001
2 0002 0002
3 0003 0003
4 0004 0004


Forklaring:

Nierkomplement (eller 9-komplement) fremstiller det negative tal ved
at erstatte hvert ciffer i det tilsvarende positive tal med dets
"9-komplement" (altså det som cifferet mangler i at være 9).

Tierkomplement (eller 10-komplement) er "odometrisk" som en tæller
på en båndoptager under tilbagespoling. Disse repræsentationer kan
man ubekymret addere.

NB! Ved 10-komplement kan man ikke negere "ciffervist", man må huske
at tage en "mente" med over fra nabocifferet når man udregner det
"modsatte" tal.

Eksempler: Find det modsatte tal til 0256:

Nierkomplement: Ciffervist, man får 9743 (hver gang det ciffer der
"mangler" for at få ni.

Tierkomplement: Udfør subtraktionen 0000-0256 (fra mindst betydende
ciffer (højre mod venstre), som i 1. klasse), det giver 9744.


Så skulle dét vist være skåret ud i pap.

--
Jeppe Stig Nielsen <URL:http://jeppesn.dk/>. «

"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)

---

Jeppe Stig Nielsen skrev:

>Øhm, jeg synes da at den sidste metode er mere intuitiv.

Du bruger en minusalgoritme til at vise det. Jeg har ikke snakket
om subtraktion.

'Alle' undrer sig over at man skal lægge 1 til når man skal finde
det negative tal i stedet for bare at vende bittene. Man kan godt
se at det virker, men der sidder stadig en lille undren tilbage.

> 356
> - 429
>________ (læses fra højre mod venstre)
>...99927

>Det er altså naturligt at repræsentere resultatet ("minus treoghalv-
>fjerds") som ...99927. Thi se selv, når man lægger ...00073 til, så
>får man jo nul.

Og så har du let og elegant overset uendelighedsproblemet. Din
udregning bliver aldrig færdig. Det er i hvert fald ikke spor
intuitivt.

>Mener du at man burde repræsentere "minus treoghalvfjerds" som
>...99926?

Jeg har slet ikke anlagt en moralsk vurdering. Jeg siger blot at
1's komplement ligger lige for hvis man selv skal regne ud
hvordan man repræsenterer negative tal. Fidusen med 2's
komplement bliver først klar når man får den forklaret og får
regnet nogle eksempler igennem, og/eller funderer over at to
forskellige 0'er kan give problemer.

>(I øvrigt må "skifte bit" (binære tal) svare til at "trække
>cifferet fra 9" (for decimale tal).)

Det kan jeg godt gå med til.

--
Bertel
http://lundhansen.dk/bertel/   FIDUSO: http://fiduso.dk/

---

Scripsit Bertel Lund Hansen <nospam@lundhansen.dk>
> Jeppe Stig Nielsen skrev:

> >Øhm, jeg synes da at den sidste metode er mere intuitiv.

> Du bruger en minusalgoritme til at vise det. Jeg har ikke snakket
> om subtraktion.

Den naturlige måde at indføre negative tal overhovedet på, er at
trække store tal fra små. Uden subtraktion, ingen negative tal.

> >Det er altså naturligt at repræsentere resultatet ("minus treoghalv-
> >fjerds") som ...99927. Thi se selv, når man lægger ...00073 til, så
> >får man jo nul.

> Og så har du let og elegant overset uendelighedsproblemet. Din
> udregning bliver aldrig færdig. Det er i hvert fald ikke spor
> intuitivt.

Jo, for maskinaritmetik er naturligt modulær.

Første gang man står overfor et ord med en endelig længde på w bits,
kan man let se at de kan repræsentere tal mellem 0 og 2^w-1. Så
spekulerer man lidt over hvad der sker med de naturlige additions-
og subtraktionsalgoritmer ved over- og underløb. Man skal beslutte
sig for hvad man gør med menter og lån, men det nemmeste er blot at
ignorere dem. Og vupti, så implementerer w-bit-ordet helt af sig selv
aritmetik modulo 2^w.

Når man så skal bruge et negativt tal, er det jo også repræsentant
for en restklasse modulo 2^w, og så tager man bare den binære
representation af denne restklasse. Tilføj en passende regel for
hvilken repræsentant for hver restklasse der er den kanoniske, og
voila - to-komplement.

> Jeg har slet ikke anlagt en moralsk vurdering. Jeg siger blot at
> 1's komplement ligger lige for hvis man selv skal regne ud
> hvordan man repræsenterer negative tal.

Hvis man er ligeglad med hvordan man regner, er det allernaturligste
da en fortegn/størrelse-repræsentation.

--
Henning Makholm "I paid off ALL my debts and bought a much-needed new car."

---

Henning Makholm wrote:
>
> Jo, for maskinaritmetik er naturligt modulær.
>
> Første gang man står overfor et ord med en endelig længde på w bits,
> kan man let se at de kan repræsentere tal mellem 0 og 2^w-1. Så
> spekulerer man lidt over hvad der sker med de naturlige additions-
> og subtraktionsalgoritmer ved over- og underløb. Man skal beslutte
> sig for hvad man gør med menter og lån, men det nemmeste er blot at
> ignorere dem. Og vupti, så implementerer w-bit-ordet helt af sig selv
> aritmetik modulo 2^w.
>
> Når man så skal bruge et negativt tal, er det jo også repræsentant
> for en restklasse modulo 2^w, og så tager man bare den binære
> representation af denne restklasse. Tilføj en passende regel for
> hvilken repræsentant for hver restklasse der er den kanoniske, og
> voila - to-komplement.

En virkelig god forklaring, synes jeg.

Jeg synes også "odometer"-billedet er godt: Hvis man har en bil der
på kilometertælleren viser "99994", véd man kun at det sande antal
kilometer er kongruent med 99994 modulo 100000. I princippet kunne
der være tale om en ny bil der bare lige havde bakket seks kilometer.

"Maskinaritmetik" svarer for mig til et odometer hvor der bare kun
er to symboler på hvert ciffer-hjul (i stedet for ti). Og da man ikke
har mulighed for at holde styr på hvor mange under- eller overløb der
har været, svarer dette (som du skriver) til modulær aritmetik.

--
Jeppe Stig Nielsen <URL:http://jeppesn.dk/>. «

"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)

---

Jeppe Stig Nielsen skrev:

>En virkelig god forklaring, synes jeg.

Det må jeg vist bekræfte. Jeg har endnu ikke fundet noget brugbar
ammunition til at skyde den ned med.

--
Bertel
http://lundhansen.dk/bertel/   FIDUSO: http://fiduso.dk/

---

Alle kaster sig nu over hinanden for at bevise hver deres metode...

Kan jeg lige spørgre igen... hvordan gør man i praksis hvis man vil finde
checksummen som er opbygget som...
"The checksum field is the 16 bit one's complement of the one's complement
sum of all 16 bit words in the header"

Jeg synes de andre indlæg er svinget mere over i retning af 2's complement,
3's complement ect ect og fortegn og ikke fortegn.

Men ellers tak for hjælpen

---

hi

Desilva wrote:
>
> Alle kaster sig nu over hinanden for at bevise hver deres metode...
>
> Kan jeg lige spørgre igen... hvordan gør man i praksis hvis man vil finde
> checksummen som er opbygget som...
> "The checksum field is the 16 bit one's complement of the one's complement
> sum of all 16 bit words in the header"
>
du går hertil:
   <http://www.rfc-editor.org/rfcsearch.html>
og taster checksum ind i søgeboksen, så får du forskellige implementationer i
tørt teknisk sprog.


--
good luck

peter

---

Scripsit "Desilva" <alamyx@softhome.net>

> Kan jeg lige spørgre igen... hvordan gør man i praksis hvis man vil finde
> checksummen som er opbygget som...
> "The checksum field is the 16 bit one's complement of the one's complement
> sum of all 16 bit words in the header"

I praksis? Man finder en Linux/GNU-implementation af den pågældende
protokol og lader sig inspirere af den.

--
Henning Makholm "De kan rejse hid og did i verden nok så flot
Og er helt fortrolig med alverdens militær"