ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Andrew Ezhguroff                     2:5020/400     21 Jul 2001  03:13:12
 To : Yuriy Kaminskiy
 Subject : Re: найти ближайшую бОльшую степень двой  ки минус 1
 -------------------------------------------------------------------------------- 
 

 Привет! "Yuriy Kaminskiy" <Yuriy.Kaminskiy@p21.f517.n5020.z2.fidonet.org>
 сообщил(а) нам:
 
 >  MA> long long f(long long t) { while(t&(t+1)) t|=(t>>1); return t; }
 >  Хех. Оно, конечно, замечательно, только работает в 1.5 раза медленнее,
 > чем вариант AM (val |= val>>1;...;val |= val>>32;) [на cyrix 6x86MX].
 >  Ключевое слово - условный переход.
 
 Тут дело не только в условии цикла, но и в том, что в варианте АМ кол-во
 операций пропорционально логарифму длины числа (на первом шаге заносится 1
 единица, на втором - 2, на третьем - 4 и т.д.), а в варианте МА -
 пропорционально длине числа (в худшем случае на каждом шаге заносится 1
 единица).
 
 С уважением, Андрей.
 --- ifmail v.2.15dev5
  * Origin: COMSTAR Telecommunications (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор