OT algoritmicka hadanka
Pavel Troller
patrol@sinus.cz
Pondělí Červen 15 14:09:03 CEST 2009
> Ako az zlozity?
>
> Uloha sice je myslena ako programatorska, s beznymi prostriedkami ktore sa daju najst v procesoroch; ale pokojne to mozeme pochopit aj ako ulohu na optimalizovanu logiku - aplikacia je sice v oboch pripadoch zriedkava, ale moze sa taka najst (nakoniec ta uloha je realna od mojho kolegu).
>
> wek
>
Zdar,
napada mne (nechce se mi to ted kodovat, tak jen slovni popis algoritmu):
- zacit s maskou s pulkou bitu 1 a pulkou 0 (napr. 0x00ff pro 16bit
promennou)
- otestovat, zda AND promenne s maskou je nenulovy a AND s negaci masky 0
nebo obracene (neplati-li, odchod)
- dle vysledku upravit masku (predpokladejme, ze platila prvni kombinace,
takze ted bude maska jen 0x000f)
- Opet provest tentyz test - tentokrate napr. vyjde druhy pripad, tj.
v dalsi iteraci bude maska 00c0
- Tento test byl pozitivni v prvnim pripade, takze zkousime 0040
- V zaverecnem testu proverime, zda to to plati a jsme hotovi.
Pokud budeme v pomocne promenne scitat vahy 8,4,2,1 nebo 0 podle toho, jak
vyjde test, jako vedlejsi produkt ziskame cislo nenuloveho bitu.
Tento algoritmus by mel jit implementovat v cyklu o poctu kroku rovnem
log2 velikosti promenne.
S pozdravem Pavel Troller
Další informace o konferenci Hw-list