Intel разослали вот такую вот головоломку:
Дано число состоящее из n битов. Нужно выяснить является ли это число целой степенью двойки.
У вас есть все элементарные действия, такие как сложение, вычитание, сдвиг, and, or, xor, nand, not и т.д. и т.п. Все эти действия делаются за О(1) сразу на все n битов. Умножение и деление в этот список не входят.
Предложите оптимальный по скорости алгоритм.
Только объясните почему ваш алгоритм работает, т.к. понимать чужие идеи всегда очень сложно.
30 октября 2009 в 16:05
Самый простой варинат:
((x – 1) & x) == 0
30 октября 2009 в 16:05
это один из простых вариантов. Приведённый здесь вариант ничуть не хуже.
30 октября 2009 в 16:04
не понял вопроса.
30 октября 2009 в 16:00
Если задача математическая и не связана с процессорами зачем брать и проверять 0100 ?
30 октября 2009 в 12:05
Anton RichDad Kononov: Да, это верное и оптимальное решение
Пздравляю!
30 октября 2009 в 12:05
легкотня какая.
вот если узнать является ли число суммой двух чисел-степеней двойки…
там чуть посложнее
30 октября 2009 в 12:05
Ты не против того как я изменил название темы?
30 октября 2009 в 12:05
хех) не против. еще есть загадочки?
30 октября 2009 в 12:05
Есть. Сейчас создам топик.
30 октября 2009 в 12:04
Владимир, ты перебираешь?
хотя мой алгоритм сложился бы так:
((not x)+1) AND x = x
условие для степеней двойки
30 октября 2009 в 12:04
Anton RichDad Kononov, я не понял, 111100000 and 000100000 = 000100000?
30 октября 2009 в 12:04
#28
если угодно называть ответы перебором, то да.
да, мой последний вариант по сути идентичен
30 октября 2009 в 12:04
Vladimir Sherbina, это опять не верно. Например для числа из 5 битов равного 8. Проверяй алгоритмы прежде чем постишь их.
30 октября 2009 в 12:04
>Anton RichDad Kononov, я не понял, 111100000 and 000100000 = 000100000?
да. потому что AND оставляет только разряды где совпадают единички, все остальные обнуляются
30 октября 2009 в 12:04
>да, мой последний вариант по сути идентичен
не совсем. берем число 0100 и прогоняем твой алгоритм (not x) + 1 == x
получаем not x = 1011
1011 + 1 = 1100
это явно не равно 0100
30 октября 2009 в 12:04
а… чтото я погнал
Смотрю на and, а думаю об or.
Так, секунду…
30 октября 2009 в 12:03
(x!=1) and ((x<<1)==0)
х – это наше число
30 октября 2009 в 12:03
#20, у тебя есть любое число. Взять число это элементарное действие.
#21, неверно. Например, если х=1, х=8.
ps: Никакой перегрузки или отрицательных чисел тут нет. Если вы сдвигаете число 16 в лево то получите число 32, даже если изначально было только 4 бита.
30 октября 2009 в 12:03
ладно, допустим число ноль у меня есть (в любом процессоре оно есть просто потому что есть)
тогда мой алгоритм будет в 4 шага:
1) B = NOT 0 (получим все 1 в разрядах, но на некоторых процессорах на целочисленных операциях можно делать ноль минус один и опять получим все 1, только не спрашивайте где взять 1)
2) Y = X xor B
3) Z = Y – 1
4) ANS = Z AND X
если ANS=X тогда – число степень двойки
30 октября 2009 в 12:03
#20, кстати операция not делает то, что ты хотел сделать с хоr 11111…1
30 октября 2009 в 12:03
Алгоритм ещё не проверял, но нет никакой связи с процессорами. Это математическая задача.
30 октября 2009 в 12:03
#22 тогда если я могу взять любое число, то три шага
поясняю суть алгоритма:
если число – это степень двойки, то все разряды нули кроме одного
например 000100000
теперь инвертируем его (например как я через XOR, ну или через NOT)
получим 111011111
теперь прибавим 1
получим 111100000
теперь к полученному сделаем AND с исходным числом
получим 000100000
30 октября 2009 в 12:03
а если вот так:
(not x) + 1 == x
?
30 октября 2009 в 12:02
Я пока плохо представляю как будет работать бинарный поиск в этом случаи, но даже если это и возможно то мы имеем О(log(n)). Не плохо… но может ктото придумает алгоритм по оптимальней?
30 октября 2009 в 12:02
Это понятно, скорее всего есть какая-то операция типа xor или nand (вот я уже не помню, что это значит даже), которая дает какой-то результат лишь если только одна единица среди n. Соответственно её надо ко всем применить за O(1), может быть пару таких операций – и сверить результат с нужным.
30 октября 2009 в 12:02
я бы делал так (допустим X – это наше число):
1) Y = X XOR 111…111 (все разряды 1) – так мы инвертируем число
2) Z = Y + 1
3) ANS = Z AND X
если ANS=X тогда это число – степень двойки
три шага получается O(3)
30 октября 2009 в 12:02
Три шага – это О(1), оптимальней не возможно. Но где ты возьмёшь число 1111….1? Чтобы составить его тебе нужно О(n) шагов. Правильность алгоритма, кстати, не проверял. Желательно объяснить почему алгоритм должен работать, т.к. проверять чужие идеи всегда очень сложно.
30 октября 2009 в 12:02
ну хорошо, а число ноль у меня хоть есть?
если есть, то нет проблем сделать из него все единицы
30 октября 2009 в 12:01
#10 Есть такие числа, которые делятся на 2, но не являются степенями двойки…
ЗЫ Задача достаточно тривиальная, надо только немного подумать
30 октября 2009 в 12:01
#11 это модно – разговаривать с собой?
30 октября 2009 в 12:01
Более того число 1 не делиться на два, младший бит равен 1, а всё равно это целая степень двойки.
Задача эта может и тривиальная, но не простая
30 октября 2009 в 12:01
видимо, #10 – это ответ мне. я запостил сообщение и сразу удалил, потому что пришло озарение и я понял, что написал чушь
30 октября 2009 в 12:01
Ну, уже прогресс
Ладно, небольшой намёк. Оптимальный алгоритм работает быстрее чем О(n) 
30 октября 2009 в 12:01
>> Предложите оптимальный по скорости алгоритм.
самое простое – бинарный поиск. то есть использовать для поиска выражения вида 1<<(n>>p)-1<<o
30 октября 2009 в 11:05
Да, подправил задачку. Все элементарные действия выполняются за О(1) сразу на все n битов.
30 октября 2009 в 11:04
Борис, ты хочешь сказать, что начинаться число может с нуля?
Тогда правильный ответ – всего одна единица среди n битов.
30 октября 2009 в 11:04
О! Это уже верно. Пол задачи щитай решил, осталось предложить оптимальный алгоритм.
30 октября 2009 в 11:03
Правильный ответ – первый бит единица, а остальные нули %)
Доказательство элементарное =) Хотя наверняка это не решение, а только "указание".
Хз как побитово работать с числами и какой из способов быстрее. На проверку каждого бита по условию задачи уйдет O(1), а всего O(n), но я не уверен, что нет способа быстрее)
30 октября 2009 в 11:03
На самом деле MSB равный еденице это не обязательное условие, но ты на верном пути
30 октября 2009 в 11:02
Если младший бит установлен в 0 значит является.
30 октября 2009 в 11:02
По-моему, младший бит покажет лишь, делится ли число на 2, а не является ли степенью 2х)
30 октября 2009 в 11:02
Т.е. младший бит – 0 – это необходимое, но недостаточное