Число со степенью двойки.

← →
ArtemESC © (2006-05-21 02:46) [0]

Как проверить является ли данное число сабжем,
используя следующий операции (+, -, *, div, mod, shl, shr, xor, and, or, not) c минимальным количеством сравнений...

← →
Johnmen © (2006-05-21 02:49) [1]

Ничего нет проще.
Все степени 2 имеют 1 и кончаются нулями до посинения....

← →
ArtemESC © (2006-05-21 02:51) [2]

Johnmen © (21.05.06 02:49) [1]
Ясно, но какою реализацию предложите?

← →
Johnmen © (2006-05-21 02:54) [3]

Двигать и смотреть, что в осадке...:)

← →
ArtemESC © (2006-05-21 02:55) [4]

Johnmen © (21.05.06 02:54) [3]
Смотреть нельзя - циклов нет...

← →
Marser © (2006-05-21 03:06) [5]

Вот второе, что пришло в голову (для Word):
if (i xor $FFFF) = ($FFFF-i) then ля-ля

← →
Marser © (2006-05-21 03:07) [6]

> [5] Marser © (21.05.06 03:06)
> Вот второе, что пришло в голову (для Word):
> if (i xor $FFFF) = ($FFFF-i) then ля-ля

Стоп. Пора спать. Отзывается :-))

← →
jack128 © (2006-05-21 03:14) [7]

ArtemESC © (21.05.06 2:55) [4]
Смотреть нельзя - циклов нет...

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

← →
ArtemESC © (2006-05-21 03:17) [8]

jack128 © (21.05.06 03:14) [7]
разрядность - 16 битов...

← →
Marser © (2006-05-21 03:18) [9]

Первое пошло:
if (i div 2 + i mod 2)= i shr 1 then степень двойки

← →
Marser © (2006-05-21 03:26) [10]

> [9] Marser © (21.05.06 03:18)
> Первое пошло:
> if (i div 2 + i mod 2)= i shr 1 then степень двойки

Нет, таки пора спать. Это уже проверка на чётность...

← →
ArtemESC © (2006-05-21 03:32) [11]

Marser © (21.05.06 03:26) [10]
Может еще подумаешь?

← →
Marser © (2006-05-21 04:04) [12]

Один ответ уже знаю. Хоть я его и понял и на бумажке разобрал, но это не мой. В общем-то, он прост, как и всё гениальное.

← →
ArtemESC © (2006-05-21 04:15) [13]

Marser © (21.05.06 04:04) [12]
>>но это не мой
не страшно...

← →
jack128 © (2006-05-21 04:26) [14]

ArtemESC © (21.05.06 3:17) [8]
разрядность - 16 битов...
Операция xor за сравнение считается?? Если нет, то можно без единого сравнения решить..

← →
ArtemESC © (2006-05-21 04:28) [15]

jack128 © (21.05.06 04:26) [14]
Покажи как...

← →
jack128 © (2006-05-21 04:38) [16]

function IsEqual(a, b: Integer): BOOL; begin Result := not BOOL((a xor b) xor 0); end; function IsPowerOf2(I: Word): boolean; begin Result := IsEqual(I, $1) or IsEqual(I, $2) or IsEqual(I, $4) or IsEqual(I, $8) or IsEqual(I, $10) or IsEqual(I, $20) or IsEqual(I, $40) or IsEqual(I, $80) or IsEqual(I, $100) or IsEqual(I, $200) or IsEqual(I, $400) or IsEqual(I, $800) or IsEqual(I, $1000) or IsEqual(I, $2000) or IsEqual(I, $4000) or IsEqual(I, $8000); end;

← →
jack128 © (2006-05-21 04:44) [17]

jack128 © (21.05.06 4:38) [16]
function IsEqual(a, b: Integer): BOOL;
begin
Result := not BOOL((a xor b) xor 0);
end;
собственно можно так: Result := not BOOL(a xor b); Просто суть в том, что xor - это тоже самое, что и <>. так что...

← →
MBo © (2006-05-21 07:33) [18]

>ArtemESC

Логика подсказывает, что нужно использовать уникальные свойства, присущие только степеням двойки. Самое простое из этих свойств указано в [1]:

Каждая степень двойки выглядит так: 10000...
Предыдущее число - вот так: 01111...
Остается скомбинировать...

← →
vidiv © (2006-05-21 08:10) [19]

> Каждая степень двойки выглядит так: 10000...
> Предыдущее число - вот так: 01111...
> Остается скомбинировать...

if i and pred(i) = 0 then степень двойки...
вроде работет :)

← →
Marser © (2006-05-21 11:18) [20]

> [19] vidiv © (21.05.06 08:10)
>
> > Каждая степень двойки выглядит так: 10000...
> > Предыдущее число - вот так: 01111...
> > Остается скомбинировать...
>
>
> if i and pred(i) = 0 then степень двойки...
> вроде работет :)

Оно самое! Только вместо pred почему бы не использовать вычитание?

if i and (i-1) = then степень двойки
И не наверно, а работает 100%. Если выставлен только один бит, то при вычитании происходит заём и соответственно, сдвиг влево того самого бита. Тогда конънкция с оригиналом даст 0.
Когда я увидел это решение, то удивился и пал духом. Потому что ничего проще просто быть не может.

← →
Marser © (2006-05-21 11:18) [21]

> if i and (i-1) = then

if i and (i-1) = 0 then

← →
Alex Konshin © (2006-05-21 12:19) [22]

Это же известный финт.
И чему вас только в школе учат?
Еще немного подумайте, и узнаете как доставать самый младший ненулевой бит.
Это вам на домашнее задание.

← →
boriskb © (2006-05-21 12:25) [23]

Marser © (21.05.06 11:18) [20]
Потому что ничего проще просто быть не может.

Лет 30 назад меня так же поразило решение задачи:

Переменная может принимать значение либо 1, либо 2
Если она 1, то присвоить ей 2
Если она 2, то присвоить ей 1
;)

← →
begin...end © (2006-05-21 13:14) [24]

> Alex Konshin © (21.05.06 12:19) [22]

> Еще немного подумайте, и узнаете как доставать самый младший
> ненулевой бит.

BSF ?
:-)

← →
Kerk © (2006-05-21 13:19) [25]

Баян. У Кнута есть готовое оптимальное решение.

← →
Marser © (2006-05-21 13:35) [26]

> [24] begin...end © (21.05.06 13:14)
> > Alex Konshin © (21.05.06 12:19) [22]
>
> > Еще немного подумайте, и узнаете как доставать самый младший
>
> > ненулевой бит.
>
> BSF ?

:-)

← →
ArtemESC © (2006-05-21 13:57) [27]

jack128 © (21.05.06 04:38) [16]
vidiv © (21.05.06 08:10) [19]
Marser © (21.05.06 11:18) [20]
Всем большой thanks - даже не думал, что так просто можно
решить - мне вообще не для Дельфи надо, а для MASM - проверить
на этапе трансляции - удовлетворяет ли константа данному требованию.

← →
Marser © (2006-05-21 14:01) [28]

Да, а выглядело как задача...
А циклы почему нельзя использовать? Ты их делать в асме не умеешь :-)

← →
Marser © (2006-05-21 14:05) [29]

Тогда, кстати, можно исполльзовать BSF вместе с BSR.

← →
ArtemESC © (2006-05-21 15:08) [30]

Marser © (21.05.06 14:01) [28]
Потому что все это делается на этапе трансляции - то есть
в объектном коде никаких проверок быть не должно, а
в зависимости от значения константы - скомпилируеться
одна или другая часть кода. А среди директив MASMa циклических структур нет...

← →
vidiv © (2006-05-21 15:30) [31]

> Всем большой thanks

MBo главное спасибо :)

← →
Marser © (2006-05-21 15:46) [32]

> [31] vidiv © (21.05.06 15:30)
>
> > Всем большой thanks
>
> MBo главное спасибо :)

[19]-[21] не подходит? :-)

← →
vidiv © (2006-05-21 17:51) [33]

> Marser © (21.05.06 15:46) [32]

Он предложил самое простое решение, но остался без "большой thanks" :)

← →
Вопрошающий (2006-05-21 18:05) [34]

> Только вместо pred почему бы не использовать вычитание?

pred быстрее работает, чем вычитание

> Вопрошающий (21.05.06 18:05) [34]

Ой.

> [34] Вопрошающий (21.05.06 18:05)
>
> > Только вместо pred почему бы не использовать вычитание?
>
>
> pred быстрее работает, чем вычитание

pred в условии не было, это раз.
На уровне скомпилированного кода одно и то же, это два.

> [33] vidiv © (21.05.06 17:51)

Гы, я просто не сразу понял, что это ты до pred додумался после совета Бориса :-)

Еще задачка для желающих. Запрограммировать ступенчатую функцию f(x), определямую на интервале 0<=x<N таким образом:
0 при 0<=x<1 1 при 1<=x<2 f(x)= 2 при 2<=x<3 3 при 3<=x<4 ... N при N-1<=x<N

> ArtemESC © (21.05.06 21:50) [38]

А черт его знает, не помню уже. Эта (или какая-то похожая) задачка когда-то встретилась мне в реале, причем функции Trunc не было, а писать двухкилометровый if - это бред, естественно. Не помню точно, в чем там был фокус, но помню, что с полчаса мозги поломать пришлось, и получилось какое-то простое и красивое решение.

> MBo © (21.05.06 21:53) [39]
Да, описка, там N-1 должно быть, конечно.

> if i and (i-1) = 0 then

В принципе работает. Только есть одно число с которым оно не будет работать.

>Юрий Зотов © (21.05.06 21:36) [37]

Не обрабатываются NaN и выход за диапазон:

function QuasiTrunc(s: Single): DWord; var access: Integer; fexp: ShortInt; Mant: Int64; begin access := PInteger(@s)^; fexp := ((access shr 23) and $FF) - 127; if fexp < 0 then Result := 0 else begin Mant := (access and $7FFFFF) or $800000; Result := (Mant shl fexp) shr 23; end; end;

> Еще немного подумайте, и узнаете как доставать самый младший
> ненулевой бит.

1 ?

> ArtemESC © (22.05.06 00:56) [43]
> SergP © (21.05.06 23:04) [41]
> Ноль?

Ага... Ноль не есть степенью как двойки, так вообще любого другого числа...

2all
Числа могут быть отрицательными :(

> [46] SergP © (22.05.06 08:12)
>
> > ArtemESC © (22.05.06 00:56) [43]
> > SergP © (21.05.06 23:04) [41]
> > Ноль?
>
>
> Ага... Ноль не есть степенью как двойки, так вообще любого
> другого числа...

Да, такой недостаток имеется. Правда устраняется он введением ещё одного условия.

Число со степенью двойки. Найти похожие ветки