Staonův svět - Detekce mocniny dvou

Tak a měl bych tu další programátorskou hříčku.

Zadání je jednoduché. Napsat v Pascalu co nejkratší program, který přečte ze vstupu celé číslo (integer) a prohlásí o něm, jestli je, nebo není mocnina dvou. Popíšu svoje řešení. Pokud někdo zná ještě nějaké lepší, sem s ním :)

  1. var
  2.   x: integer;
  3. begin
  4.   read(x);
  5.   write(x = -x and x)
  6. end.

Magická formulka, že? :) Je postavena na doplňkovém kódu. „Lidský“ postup pro převedení do doplňkového kódu je následující:

  1. začnu od nejnižšího řádu binárního čísla opisovat nuly.
  2. poté, co padnu na první jedničku, přepíšu ji také.
  3. dále už přepisuji negace jednotlivých bitů.

Pakliže provedu bitový logický součin x a x v doplňkovém kódu, ve výsledku zůstane pouze nejnižší jednička – nižší bity byly nula, u vyšších násobím něco se svou negací, což je také nula. No a protože mocnina dvou má v binárním kódu pouze jednu jedničku, tak se touto operací nezmění. Bohužel má předchozí formulka ještě jeden problém: prohlásí, že i nula je mocninou dvou :( Proto je potřeba přidat ještě asi tak deset znaků a vznikne toto:

  1. var
  2.   x: integer;
  3. begin
  4.   read(x);
  5.   write((x > 0) and (x = -x and x))
  6. end.
Staon | 19.11.2005 So 12:59 | <<< trvalý odkaz >>> | tisk | 8 komentářů

Komentáře k textu

Rss komentářů tohoto textu

[1] reaguj
Jimi mejl web 19.11.2005 So 16:13

Sice som mal z predmetu kde sme sa zaoberali doplnkovym a inymi kodmi jednotku, ale to neznamena ze viem co za kod to je a sorry ale ten tvoj lidsky postup je na mna v sobotu moc :D Nicmenej, ja by som to robil tak ze by som to cislo prehnal odmocninou az by som dostal cistu 1 :-)) Jednoduchy while :P

[2] reaguj
Staon mejl web 19.11.2005 So 21:24

[1] Jimi : doplňkový kód není tak složitý ;) Ja jsem zase zkousel prohnat to cislo dvojkovym logaritmem, ale mel jsem problémy se zaokrouhlováním, nepracovalo to dobře. Taky jsem zkoušel dělit dvojkou a sčítat zbytky. Ale oboje metody byly o dost delší než tahle :)

[3] reaguj
dawon web 20.11.2005 Ne 14:22

Chjo, jsem úplně mimo :-) Co je to Pascal? ;-)

[4] reaguj
Staon mejl web 20.11.2005 Ne 15:31

[3] dawon : Pascal je programovací jazyk ;)

[5] reaguj
Jimi mejl web 20.11.2005 Ne 16:16

Tak takuto odpoved som necakal ani v najtajnejsich snoch :D fakt necakane :D

[6] reaguj
Staon mejl web 20.11.2005 Ne 16:49

[5] Jimi : No vidíš, aspoň ses dnes dozvěděl něco nečekaného :-D

[7] reaguj
Alternatíva
Peter Piják mejl web 10.1.2006 Út 22:39

Alebo synonymum k „x = -x and x“ môže byť aj „x and(x-1)“

[8] reaguj
Staon mejl web 15.1.2006 Ne 15:11

[7] Peter Piják : Díky, to vypadá ještě jednodušší a není to závislé na doplňkovém kódu :)

Přidej komentář!

  Gravatar povolen.

Příspěvěk je formátován Texy! syntaxí. Není povoleno HTML, odkazy se převádějí automaticky.
Matfyz je sbírka čeho?
Odpověd: naprostých cvoků malých červených kulatých kostiček

Autor vzhledu: Staon. Stránky jsou postaveny na redakčním systému RS2 (verze RC2).