C - прикол

[psilogic]

Как быстро проверить, является ли число степенью двойки?
На входе дано беззнаковое целое ненулевой разрядности, допускающее все операции языка C для типа unsigned. На выходе должно быть bool.

Циклы, ясное дело, не приветствуются. Мой ответ пока заскринен.

Comments

[psilogic.livejournal.com]

value && (value & (value - 1))

[phantomer.livejournal.com]

value = 8(dec) = 100(bin)

100 && (100 & 011) = false

Наверное имелось в виду: value && !(value & (value-1))

Но поюзанное свойство мне очень понравилось. Действительно, тольуо у степени двойки при декременте обнуляется старший бит. У прочих чисел он остаётся установленным. Респект.

[psilogic.livejournal.com]

Ахха, что-то типа того. Еще бы от логических операций типа "&&" уйти... это же условный переход по идее

[phantomer.livejournal.com]

Попарил моск. Без явного или косвенного сравнения не придумалось.

[psilogic.livejournal.com]

:))

[myrix-et-al.livejournal.com]

x & (x - 1) - обнуляем младший бит
Соответственно !( x & (x - 1) ) - в числе нет битов, кроме младшего, что нам и требуется

[psilogic.livejournal.com]

гут! :)
осталось исправить баг: ноль - не степень двойки, а он под эту формулу подходит

[sphinks82.livejournal.com]

ну этот баг легко убирается вроде:
!( x & (x - 1) ) && x

[psilogic.livejournal.com]

угумс :)

[charon.livejournal.com]

Ассемблерной вставкой: вычесть 1 и посмотреть флаг четности.

[psilogic.livejournal.com]

смотря что этот флаг показывает...

[charon.livejournal.com]

четность операции.

[charon.livejournal.com]

а, нет. Вру.

[charon.livejournal.com]

надо не вычитать, надо делить.

[esyr.livejournal.com]

А при чём здесь Си? Лично у нас подобные радости жизни на практикуме по ассемблеру были.

[sillykong.livejournal.com]

С - символический ассемблер. )

[psilogic.livejournal.com]

гы :)

[psilogic.livejournal.com]

Си способен на многое :)

[arifg.livejournal.com]

О, это хорошая задача. Правда, когда я ее впервые услышал, условие было написать код из трех команд на ассемблере (включая условный переход), а не на С. У меня заняло где-то 15 минут, чем я был очень горд :)

[sezam_lj.livejournal.com]

Аппаратным логарифмированием :)

[psilogic.livejournal.com]

=))

[minimuk.livejournal.com]

!(value && 1) ?
Оставляем первый бит получаем нечетное число,
не_нечетно => четное