|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Max Alekseyev 2:5015/60 20 Jul 2001 16:11:58
To : Yuriy Kaminskiy
Subject : найти ближайшую бОльшую степень двойки минус 1
--------------------------------------------------------------------------------
Replying to a message of Yuriy Kaminskiy to Max Alekseyev:
АМ>> Число - целое 8 байт (Int64) АМ> необх найти ближайшую бОльшую
АМ>> степень двойки минус 1, т.е. АМ> для 4...7 - это 7; АМ> для
АМ>> 32...63 - это 63;
MA>> вот навскидку:
MA>> long long f(long long t) { while(t&(t+1)) t|=(t>>1); return t; }
YK> Хех. Оно, конечно, замечательно, только работает в 1.5 раза
YK> медленнее, чем вариант AM (val |= val>>1;...;val |= val>>32;) [на
YK> cyrix 6x86MX].
Это на каких данных? Время усредненное?
YK> Ключевое слово - условный переход.
Ok. A так?
long long f2(long long t)
{
long long z = t;
while(z) t|=(z>>=1);
return t;
}
Или так?
long long f3(long long t)
{
long long z;
while(t) t &= (z=t-1);
return z|(z+1);
}
Regards, ш.ш
Max ~
--- OS/2 Uptime: 0d 1h 25m 31s 828ms
* Origin: Он в водке тонет, а сам не плотит. (2:5015/60)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
