"Искусство программирования" (задача 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;

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