Форум PHP программистов

[ Поиск ] - [ Пользователи ] - [ Календарь ]

linker

3.03.2011 - 17:14

Твина упоминание о softtime заставили меня узнать, что это. Гуляя по сайту, обнаружил интересную, с моей точки зрения, старую задачу. Я её обрезал ровно в два раза и получилось следующее:

Нужно написать конвертер десятичного числа в двоичное представление, но с условием: можно пользоваться всем, кроме вызова функций, т.е. вообще без использования каких бы-то ни было функций.

Хорошая простая задачка на простейшую логику.

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

P.S. Подогрею, у меня получилась одна строчка кода, без учета инициализации и вывода результата.

Спустя 3 часа, 46 минут, 57 секунд (3.03.2011 - 20:01) glock18 написал(а):

linker
ну ты и силен

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

будет время подумаю над тем, как можно в одну строку решить

Спустя 1 час, 6 минут, 37 секунд (3.03.2011 - 21:07) linker написал(а):

glock18

нет у меня все в приделах правил. Добавлю, даже без единой "{" и "}".

Спустя 1 час, 18 минут, 51 секунда (3.03.2011 - 22:26) inpost написал(а):

Сколько лет вы занимаетесь программированием? Линкер, Глок?

Ато я даже не понял, что надо перевести в 1010101 код?

Спустя 3 минуты, 26 секунд (3.03.2011 - 22:30) linker написал(а):

inpost
Ну допустим есть $a = 44353 нужно написать аналог стандартной PHP-функции decbin(), которая переводит число из десятичной системы в двоичную, но без использования каких-либо функций.

Спустя 38 минут, 20 секунд (3.03.2011 - 23:08) Invis1ble написал(а):

Я щас кофе попью и попробую решить )

Спустя 2 минуты, 59 секунд (3.03.2011 - 23:11) Invis1ble написал(а):

linker
а десятичное число может быть любым?

Спустя 6 минут, 45 секунд (3.03.2011 - 23:18) ApuktaChehov написал(а):

(int) можно юзать?

Спустя 5 минут, 47 секунд (3.03.2011 - 23:24) linker написал(а):

Десятичное число - это десятичное число, и оно не может быть никаким другим

. Можно юзать все, кроме вызовов функций.

Спустя 2 минуты, 2 секунды (3.03.2011 - 23:26) ApuktaChehov написал(а):

я не знаю является ли (int) функцией, т.е. не уверен. Фактически это конструкция, но хз, по этому и спрашиваю.

Спустя 11 минут, 8 секунд (3.03.2011 - 23:37) Trianon написал(а):

Цитата (linker @ 3.03.2011 - 13:14)

P.S. Подогрею, у меня получилась одна строчка кода, без учета инициализации и вывода результата.

40 символов кода.
75 - если оформить функцией

Спустя 55 секунд (3.03.2011 - 23:38) inpost написал(а):

Я сделал =) Всё красиво оформил, получилось сама операция (без инициализации) на 14 строк, 95 символов =)

Спустя 9 секунд (3.03.2011 - 23:38) linker написал(а):

Это не функция.

Спустя 4 минуты (3.03.2011 - 23:42) linker написал(а):

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

P.S. Точнее не в обед, а ровно через сутки.

Спустя 30 секунд (3.03.2011 - 23:42) inpost написал(а):

linker
Ты хоть скажи, я решил эту задачу?!

Спустя 16 часов, 20 минут, 8 секунд (4.03.2011 - 16:02) linker написал(а):

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

inpost

$x = 25252;
$line = '';
while($x > 1)
{
    if($x%2)
    {
        $line = '1'.$line;
        $x = $x/2 - 0.5;
    }
    else
    {
        $line = '0'.$line;
        $x = $x/2;
    }
}
$line = $x.$line;
echo $line;

ApuktaChehov

while(($int = (int)$int / 2) > 0) $a = ($int * 2 - (int)$int * 2) . $a;

Invis1ble

$dec = 254;
for ($i = $dec, $bin = ''; $i > 0; $bin = $i % 2 . $bin, $i = ($i - $i % 2) / 2) {}
echo '<br />' . $bin;

glock18

$n = (int)5235325197632532;
for ($i = 1, $binary = ''; $n >= $i; $i = $i << 1) $binary = ($i & $n ? '1' : '0') . $binary;
echo $binary . '<br />';

Trianon

$s=''; 
$k = 32; 
do $s=($n&1).$s; while(--$k && $n>>=1);

ну и мой вариант

$bits = 32;
$res = '';
$dec = 1234;
do $res = $dec & 1 ? 1 . $res : 0 . $res; while(-- $bits && $dec = $dec >> 1);
echo $res;

Спустя 1 час, 10 минут, 19 секунд (4.03.2011 - 17:13) inpost написал(а):

А зато в моём варианте всё предельно ясно! =) Любой дурак разберётся! =)))
А что значат строки: $i = $i << 1 , $n>>=1 ? (если знак больше-меньше, то почему их 2?
Как понять: $n&1 ?

Спустя 43 минуты, 30 секунд (4.03.2011 - 17:56) glock18 написал(а):

Цитата (inpost @ 4.03.2011 - 14:13)

А что значат строки: $i = $i << 1 , $n>>=1 ?

$i = $i << 1 это то же самое что $i <<= 1;

побитовый сдвиг влево.

различаются все равно что $i = $i + 1 и $i += 1;

Цитата (inpost @ 4.03.2011 - 14:13)

Как понять: $n&1 ?

это побитовое and.

Спустя 7 минут, 2 секунды (4.03.2011 - 18:03) Trianon написал(а):

P & Q - операция поразрядного логического И.
в результате будет число, в котором каждый двоичный разряд равен 1 если соответствующие разряды и в P и Q оба равны 1 (и будет равен 0 если хотя бы в одном из операндов соответствующий разряд равен 0).

соответственно, $n&1 равно единице для нечетных $n и нулю - для четных.

P >> Q - операция поразрядного [арифметического] сдвига числа P вправо на Q двоичных разрядов.
<< - то же самое, но влево.

>>= , <<= - аналогичные операции, но с присваиванием резльтата левому операнду. Как +=

Спустя 2 часа, 31 минута, 30 секунд (4.03.2011 - 20:35) inpost написал(а):

Спасибо за объяснения.
Если вдруг кому-то будет интересно, поделюсь результатом по производительности:
http://inpost.dp.ua/12/test3.php

INVIS - не заработал скрипт, я не смог его запустить...
glock18 - очень медленно на моём хостинге, падал даже на числе выше 7-8 символов (без циклов, при этом все предыдущие проходили цикл 1000). Поэтому убрал из статистики.

Спустя 1 час, 36 секунд (4.03.2011 - 21:35) glock18 написал(а):

Цитата (inpost @ 4.03.2011 - 17:35)

glock18 - очень медленно на моём хостинге, падал даже на числе выше 7-8 символов (без циклов, при этом все предыдущие проходили цикл 1000). Поэтому убрал из статистики.

надо было "защиту от дурака" сделать на подобие линкера и трианона, чтобы всякие разные личности не просили 53битовое число в 32битах хранить

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

PS: добавил мега-защиту в пост линкера

Спустя 58 минут, 47 секунд (4.03.2011 - 22:34) inpost написал(а):

glock18
Ты не обижайся, я только учусь, решил сравнить, на сколько именно мой результат хуже, чем перебор по битовый, как сделали эксперты.
Я для себя сделал, посмотрел, решил просто поделиться, а не брал как эталон. Там и обычное число 10 обрабатывалось 4 секунды (один цикл)

Спустя 2 часа, 2 минуты, 28 секунд (5.03.2011 - 00:37) inpost написал(а):

Обновил результаты, если кому-то вдруг стали интересны, добавил Глока и Инвиза.

Спустя 11 часов, 21 минута, 22 секунды (5.03.2011 - 11:58) Trianon написал(а):

как все эти фрагменты работают при отрицательных величинах в переменной?

Спустя 2 минуты, 42 секунды (5.03.2011 - 12:01) glock18 написал(а):

Цитата (Trianon @ 5.03.2011 - 08:58)

как все эти фрагменты работают при отрицательных величинах в переменной?

тоже задавался таким вопросом

Спустя 3 дня, 22 часа, 15 минут, 22 секунды (9.03.2011 - 10:16) linker написал(а):

glock18
Нет, результат не обрежется. PHP оперирует целыми знаковыми числами от -2147483648 до 2147483647, а это и есть те самые 32 бита.

Спустя 6 часов, 6 минут, 29 секунд (9.03.2011 - 16:23) glock18 написал(а):

linker
ну я это и имел ввиду, а про 32бита я выше уже говорил. в примере изначально было что-то типа 5893580938509830, и битов в результате обработки этого как числа будет всего 32 при 4байтовом инте, чего очевидно недостаточно для такого числа. вот и обрежется, считай, число то изначальное

Спустя 20 минут, 31 секунда (9.03.2011 - 16:43) Trianon написал(а):

5893580938509830 - с точки зрения представления данных в php - целым числом быть не может. Может являться только либо строкой либо числом вещественным.
В исходной задаче же речь шла о целых числах.

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

Отрицательные числа, тем не меннее вполне себе предстваимы, и особых оговорок для них в постановке вроде как не было (а зря). Но вот то, как ведут себя перечисленные фрагменты кода - вопрос отдельный. Сдается мне, там не всё так гладко.

_____________
Gear Framework
Gear Framework на Github

Быстрый ответ:

Здесь расположена полная версия этой страницы.