Предыдущее питание 2
Существует большая информация о том, как найти следующее питание 2 из данного значения (см. судей), но я не могу найти, что любой получает предыдущее питание два.
Единственным путем я нахожу, до сих пор должен сохранить таблицу со всем питанием два до 2^64 и сделать простой поиск.
3 ответа
Это мое текущее решение для нахождения следующей и предыдущей степеней двойки любого заданного положительного целого числа n, а также небольшая функция для определения того, является ли число степенью двойки.
Эта реализация предназначена для Ruby.
class Integer
def power_of_two?
(self & (self - 1) == 0)
end
def next_power_of_two
return 1 if self <= 0
val = self
val = val - 1
val = (val >> 1) | val
val = (val >> 2) | val
val = (val >> 4) | val
val = (val >> 8) | val
val = (val >> 16) | val
val = (val >> 32) | val if self.class == Bignum
val = val + 1
end
def prev_power_of_two
return 1 if self <= 0
val = self
val = val - 1
val = (val >> 1) | val
val = (val >> 2) | val
val = (val >> 4) | val
val = (val >> 8) | val
val = (val >> 16) | val
val = (val >> 32) | val if self.class == Bignum
val = val - (val >> 1)
end
end
Пример использования:
10.power_of_two? => false
16.power_of_two? => true
10.next_power_of_two => 16
10.prev_power_of_two => 8
Для предыдущей степени двойки поиск следующей и деление на два происходит немного медленнее, чем описанный выше метод.
Я не уверен, как это работает с Bignums.
Вероятно, самый простой подход (для положительных чисел):
// find next (must be greater) power, and go one back
p = 1; while (p <= n) p <<= 1; p >>= 1;
Вы можете вносить изменения разными способами, если хотите оптимизировать.
Из Hacker's Delight , хорошее решение без ответвлений :
uint32_t flp2 (uint32_t x)
{
x = x | (x >> 1);
x = x | (x >> 2);
x = x | (x >> 4);
x = x | (x >> 8);
x = x | (x >> 16);
return x - (x >> 1);
}
Обычно для этого требуется 12 инструкций. Вы можете сделать это с меньшими затратами, если в вашем ЦП есть инструкция «подсчитывать ведущие нули».