Здесь я хочу рассказать и обсудить несколько алгоритмов для нахождения старшего единичного бита числа.
На всякий случай, поясню: старшим битом называется единичный бит числа, отвечающий за самую большую степень двойки. Иными словами, это самая большая степень двойки, не превосходящая числа. Чтобы избежать многих случаев, будем здесь считать, что мы имеем дело с натуральным числом в пределах от 1 до 2^31 — 1 включительно. Кроме того, чтобы не слишком углубляться в теорию вероятности, будем считать, что число, в котором требуется определить старший бит, с одинаковой вероятностью будет любым из возможных чисел.
Для начала, рассмотрим самый простой, первым приходящий в голову алгоритм. Давайте переберём все степени двойки, и выберем из них максимальную, которая не превосходит числа. Здесь, очевидно, можно воспользоваться монотонностью этого свойства, то есть тем, что если какая-то степень двойки не превосходит числа, то и меньше степени и подавно не превосходят. Поэтому, это метод можно написать очень просто:
int bit1(int x) {
int t = 1 << 30;
while (x < t) t >>= 1;
return t;
}
Обнаружение пешеходов используется главным образом в исследованиях, посвященных беспилотным автомобилям. Общая цель обнаружения пешеходов — предотвращение столкновения автомобиля с человеком. На Хабре недавно был топик про «умные машины». Создание подобных систем очень популярное направление исследований (Darpa challenge). Я занимаюсь распознаванием пешеходов для подобного проекта интеллектуальных автомобилей. Очевидно, что проблема обнаружения пешеходов — программная, а предотвращение столкновения — аппаратная. В данной статье я упомяну лишь о программной части, кратко расскажу об одном способе обнаружения людей на изображении и алгоритме классификации.
Итак, мы постепенно выходим на финишную прямую сборки Кубика Рубика 5х5х5! Осталось дособирать рёбра куба и центральные квадраты. Кроме того, есть программа-эмулятор кубика, так что даже если куба нет, можно попробовать собрать его на ПК.
В прошлый раз мы говорили о том, что число бинарных деревьев с n вершинами равно C(n), где C(n) – это n-ое число Каталана. Я заинтересовался чего больше: произвольных деревьев из n вершин или бинарных деревьев из n вершин. Ответ может вас удивить, он не лежит на поверхности.
