Division med två

Från Wikipedia
Hoppa till: navigering, sök

Division med två är inom matematik en operation som historiskt sett ansetts viktig. Inom programmering studeras ofta problemet separat från allmän division, på grund av att division med 2 är lätt att utföra i det binära talsystemet.

Binärt talsystem[redigera | redigera wikitext]

Inom binära talsystemet kan ett tal enkelt delas med två genom att göra ett bitskift åt höger. Exempelvis är talet 194 i binärt 11000010 och 194 / 2 = 97 är 01100001. Likaså är 97 / 2 = 48,5 i binärt 110000,1. I datorer representeras heltal oftast som fixtal och därför försvinner halvan när man gör ett högerskift på ett udda tal (dock sätts oftast en flagga för att markera att en bit skiftades ut). Exempelvis hade ett högerskift på talet 110001 (97) gett resultatet 110000 (48).

Mer allmänt kan man i det binära talsystem dela med en tvåpotens 2k genom att göra k högerskift. Säg att man har ett heltal a, som i binär form är anan-1 ... a1a0, dvs a kan skrivas:

a = 2^n a^n + 2^{n-1} a_n + \dots + 2 a_1 + a_0 = \sum_{m=0}^n a^m 2^m.

Om man nu delar med 2k får man:

\frac{a}{2^k} = \frac{1}{2^k} \sum_{m=0}^n a_m 2^m = \sum_{m=0}^n a_m 2^{m-k} = 2^{n-k} a_n + 2^{n-k-1} a_{n-1} + \dots + 2^{1-m} a_1 + 2^{-m} a_0

Vilket motsvarar k högerskift av anan-1 ... a1a0.

Ett flyttal med basen 2 kan delas med 2 genom att subtrahera 1 från exponenten.

Decimalt talsystem[redigera | redigera wikitext]

Följande algoritm kan användas för att dela ett tal N med 2:

  • Skriv ut N och sätt en nolla längst till vänster.
  • Gå igenom talen i N i överlappande par och skriv ner tal enligt nedanstående tabell:
Om första talet är Jämnt Udda
och andra talet är 0 eller 1 2 eller 3 4 eller 5 6 eller 7 8 eller 9 0 eller 1 2 eller 3 4 eller 5 6 eller 7 8 eller 9
skriv 0 1 2 3 4 5 6 7 8 9

Exempel: Vad är 1738 / 2?

  • Skriv 01738.
  • Första paret är 01. 0 är jämnt, skriv 0.
  • Andra paret är 17. 1 är udda, skriv 08.
  • Tredje paret är 73. 7 är udda, skriv 086.
  • Sista paret är 38. 3 är udda, skriv 0869.

Svaret är alltså 1738 / 2 = 869.

Källor[redigera | redigera wikitext]

Den här artikeln är helt eller delvis baserad på material från engelskspråkiga Wikipedia
Venn A intersect B.svg Matematikportalen – portalen för matematik på svenskspråkiga Wikipedia.