Division med två

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

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 2^k genom att göra k högerskift. Säg att man har ett heltal a, som i binär form är a_na_n-1 ... a₁a₀, dvs a kan skrivas:

$a=2^{n}a^{n}+2^{n-1}a_{n}+\dots +2a_{1}+a_{0}=\sum _{m=0}^{n}a^{m}2^{m}.$

Om man nu delar med 2^k 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 a_na_n-1 ... a₁a₀.

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

Decimalt talsystem

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

Den här artikeln är helt eller delvis baserad på material från engelskspråkiga Wikipedia, tidigare version.