"Искусство программирования" (задача 1)

[vimmax]

Вопрос №1: Написать подпрограмму, проверяющую, является ли число степенью 2 (т.е. числа 2=2¹, 4=2², 8=2³, 16=2⁴ и т.д.).
Условия:
1. Реализацию этого алгоритма можно предложить на любом языке программирования. Алгоритм должен выдавать Да/Нет (т.е 0/1, True/False кому как удобнее). Мой ответ на ANSI С.
2. Подпрограмма должна быть оптимизирована по времени (т.е. минимальное время выполнения).
3. Время проверки НЕ ДОЛЖНО зависеть от типа проверяемой переменной (byte, short, int, long int) и НЕ ДОЛЖНО зависеть от величины проверяемой переменной.

Примечания: ответы типа "у меня на P4-3000Mhz время одинаковое" - не принимаются.

[grimgav]

Проверяем младший бит. Возвращаем true если мл. бит 0, иначе false.

Извините без программного кода. Главное алгоритм %)

[vimmax]

grimgav - Ответ #1 -> твой алгоритм определяет четное число или нечетное. Число 6 по твоему алгоритму выдаст True, хотя оно не является степенью двойки.

[grimgav]

grimgav - Ответ #1 -> твой алгоритм определяет четное число или нечетное. Число 6 по твоему алгоритму выдаст True, хотя оно не является степенью двойки.

Гыы %) shame on me )))

[vimmax]

У кого-нибудь есть вообще какие-нибудь соображения на эту тему?

[Storm]

ИМХО, за одинаковое количество команд ассемблера для 8,16, 32 и 64 битных целых не получится - обработка должна быть либо пословная либо побайтовая. Надо проверить на количество единиц в двоичном виде, если больше 1, то не степень.

[Sochin]

ИМХО, за одинаковое количество команд ассемблера для 8,16, 32 и 64 битных целых не получится - обработка должна быть либо пословная либо побайтовая. Надо проверить на количество единиц в двоичном виде, если больше 1, то не степень.

В таком случае алгоритм зависит от конкретной реализации типов данных в двоичном представлении. ))

[vimmax]

Предложите какой-нибудь алгоритм, на его примере буду давать подсказки.
Надо от чего-то оттолкнуться.

[EvilMax]

Я думаю, следует уточнить разрешенные при решении операции. Вычислить логарифм по основанию 2 и проверить, что его дробная часть равна 0 нехитро.

[Sochin]

Я думаю, следует уточнить разрешенные при решении операции. Вычислить логарифм по основанию 2 и проверить, что его дробная часть равна 0 нехитро.

А вычислить логарифм посредством элементарных операций сильно хитро? ))

[EvilMax]

А вычислить логарифм посредством элементарных операций сильно хитро? ))

Вот поэтому и есть просьба уточнить задание.

[Sterh]

Предложите какой-нибудь алгоритм, на его примере буду давать подсказки.
Надо от чего-то оттолкнуться.

А что тут непонятного?
Storm предложил хороший вариант!
Я - За =Р

з.ы. Storm - требуй плюсик и Канары! ))

[vimmax]

Вычислить логарифм по основанию 2 и проверить, что его дробная часть равна 0 нехитро.

EvilMax - Ответ #8 -> а есть ли гарантия что операция вычисления логарифма не зависит от типа переменной и от величины числа? Ты ведь не знаешь реализацию кода этой функции.

ИМХО, за одинаковое количество команд ассемблера для 8,16, 32 и 64 битных целых не получится - обработка должна быть либо пословная либо побайтовая. Надо проверить на количество единиц в двоичном виде, если больше 1, то не степень.

Storm - Ответ #5 -> Мдааа.. ну это слишком глубоко пошло. Конечно элементарные операции для байтов, слов и двоичных слов будут использовать различное машинное время, хотя для современных процессоров все может уложится в один такт

[vimmax]

Sterh -> плюсика еще рано

Storm указал на суть задачи, все дело в битовом представлении чисел.

Если кому-то несложно, то напишите плиз несколько чисел степени двойки, в двоичном представлении. Потом несколько чисел, которые больше этого числа, и несколько чисел которые меньше этого числа. Это подсказка.

[BODROV]

Если кому-то несложно, то напишите плиз несколько чисел степени двойки, в двоичном представлении. Потом несколько чисел, которые больше этого числа, и несколько чисел которые меньше этого числа. Это подсказка.

не, ну то, что число степени двойки в двоичном виде - это единица и нолики (10, 100, 1000) эт ясно. но меня чет сбило с толку это:

3. Время проверки НЕ ДОЛЖНО зависеть от типа проверяемой переменной (byte, short, int, long int) и НЕ ДОЛЖНО зависеть от величины проверяемой переменной.

[Sochin]

Storm - Ответ #5 -> Мдааа.. ну это слишком глубоко пошло. Конечно элементарные операции для байтов, слов и двоичных слов будут использовать различное машинное время, хотя для современных процессоров все может уложится в один такт

Хе-хе.

Примечания: ответы типа "у меня на P4-3000Mhz время одинаковое" - не принимаются.

[vimmax]

ОК, давайте вопрос о типах данных пока замнем. Поговорим о нем когда увидите решение. Условно можно принять тип данных int.

Однако решение, которое я знаю, точно самое оптимальное и его скорость не зависит от величины проверяемой переменной.

Мою подсказку(ответ #13) проигнорировали полностью....

[BODROV]

есть идея, только проверять не хочеться
х - заданное число
если ((х-1) xor (x)) равно ((x-1)+x) тогда это степень двойки

[vimmax]

Проверять не хочется - тогда я буду вам компилятором чтоли?
BODROV - Ответ #17 -> молодец, это правильное направление.

Надо упростить: заменить некоторые операторы, а другие ваще убрать. И напишите программным кодом, как-нибудь стандартизировано - дело надо до конца доводить.

[BODROV]

гы, подправил

procedure TForm1.Button1Click(Sender: TObject);
var
  x: longint;
begin
  x:=strtoint(edit1.text);
  if ((x-1) xor x) = ((x shl 1)-1)
  then label1.Caption:='true'
  else label1.Caption:='false';
end;

время так и не получилось посчитать, давно не кодил - не помню, а разбираться нет времени

[grimgav]

Оффтоп: от увиденного выше вспомнилось How the way people code "Hello World" varies depending on their age and job.

[vimmax]

BODROV - Ответ#19 - та время засекать не надо. Просто писать в виде кода достаточно.

Данный ответ не зависит от величины переменной, т.е. скорость проверки будет одинаковой как для 4, так и для 1024. Но в моем ответе всего 3 операции.
а в твоем ((x-1) xor x) = ((x shl 1)-1)    -  5 операций.

Надо еще минимизировать.

[Sochin]

а для

BODROV - Ответ#19 - та время засекать не надо. Просто писать в виде кода достаточно.

Данный ответ не зависит от величины переменной, т.е. скорость проверки будет одинаковой как для 4, так и для 1024. Но в моем ответе всего 3 операции.

А для 2^(10^1024)? )))

[BODROV]

хух.... кажись родил.....

(x and (x-1)) = 0

[vimmax]

BODROV - Ответ #23 -> ну родил так родил!!! отлично, правильный ответ.
BODROV +1.

только мой вариант C, но это то же самое:
#define isPower2(x)   ( !( (x) & ((x)-1) )  )

Так'с, теперь когда известен правильный ответ, будем обсуждать вопрос о скорости выполнения этого кода для различных типов данных и различных величин?

[Tuomas]

Сначала укажите область практического применения данного примера

[Alder]

Сначала укажите область практического применения данного примера

Да где угодно,но особенно такая эффективность нужна при программировании для микроконтроллеров (ИМХО)

[Storm]

BODROV - Ответ #23 -> ну родил так родил!!! отлично, правильный ответ.
BODROV +1.

только мой вариант C, но это то же самое:
#define isPower2(x)   ( !( (x) & ((x)-1) )  )

Так'с, теперь когда известен правильный ответ, будем обсуждать вопрос о скорости выполнения этого кода для различных типов данных и различных величин?

Как говорится, классика...

На ассемблер это развернется в хз скоко команд в зависимости от разрядности используемого процессора и разрядности переменной х.

ЗЫ: Есть хорошая книга "Алгоритмические трюки для программистов", там большая часть таких изгибов ума разобрана от и до.

[vimmax]

Правильно сказал Alder, данная эффективность и прочие похожие трюки подходят при embedded программировании для контроллеров и мобильных систем.

Но не все знают, что подобные трюки любят спрашивать программисты при собеседовании на работу. Так что, советую всегда хранить в голове.

[Sochin]

А еще, также возможно не все знают, что множество дефайнов по сути - это источник проблем, так как не осуществляется никакой проверки типов/параметров и при достаточно большом размере проекта множество дефайнов делают развитие проекта непредсказуемым.
Вобщем, фтопку дефайны как и оператор goto.

[vimmax]

Вобщем, фтопку дефайны как и оператор goto.

Нельзя так резко отзываться об инструментах программирования. В ANSI C нет понятия inline функций, поэтому использование #define макроса вместо функции экономит стековую память и скорость вызова (за счет макроподстановки).

[Sochin]

Нельзя так резко отзываться об инструментах программирования. В ANSI C нет понятия inline функций, поэтому использование #define макроса вместо функции экономит стековую память и скорость вызова (за счет макроподстановки).

Я же написал для проектов достаточно большого размера и сложности. Для простеньких программ - ради Бога, как и вышеупомянутый оператор, справедливо раскритикованный много лет назад одним из уважаемых профи.

[vimmax]

Sochin - а что для тебя есть "проектов достаточно большого размера и сложности" ? Например проект из 231 исходника для гигабитного маршрутизатора MARVELL серии ExMxPm является достаточно большим и сложным? (кстати, он еще в продажу не поступил)

Я думаю ты бы не обрадовался если бы маршрутизатор твоей сети работал на 5% медленнее, чем сейчас

[Tuomas]

действительно, от goto уже многие отказались, и скоро, я думаю, этот оператор канет в Лету.

[mars]

BODROV - Ответ #23 -> ну родил так родил!!! отлично, правильный ответ.
BODROV +1.

только мой вариант C, но это то же самое:
#define isPower2(x)   ( !( (x) & ((x)-1) )  )

Так'с, теперь когда известен правильный ответ, будем обсуждать вопрос о скорости выполнения этого кода для различных типов данных и различных величин?

Хороший ответ если исключить 0.
al = х = 0 ->  00000000b
bl = x-1=-1 -> 11111111b
al and bl = 00000000b
но 0 не является степенью 2.

[BODROV]

но 0 не является степенью 2.

ээээээ, а разве 0² != 0 ?

[Sochin]

ээээээ, а разве 0² != 0 ?

Это квадрат нуля, а не степень двойки. )

[BODROV]

Это квадрат нуля, а не степень двойки. )

да, протупил!

[mars]

Хотелось бы первый + ))

[Storm]

действительно, от goto уже многие отказались, и скоро, я думаю, этот оператор канет в Лету.

в ЯВУ отказались, в Ассемблере он как был, так никуда не делся и не денется.... ибо в линейной памяти  джамп замены не имеет...