еще одна задачка

[avva]

Эта запись будет интересна только программистам (ну или еще может математикам). Задача не особенно сложная, комменты скрывать не буду, не смотрите туда, если не хотите спойлеров.

Задача: написать функцию f(x), так, что f(f(x) = -x. Разрешено использовать только
целые числа. x - целочисленный аргумент (например, 32-битный).

Update: интересно, что никто, кажется, не дал правильного решения для 32-битных чисел (для "вообще целых чисел" правильных решений куча).

Update: неудивительно, потому что для 32-битных решения нет! :) У меня был глюк.

Comments

[aburachil.livejournal.com]

Математикам едва ли, всё ж таки умножение на i проходят на первом курсе :-)

[dragon-ru.livejournal.com]

И при этом получается целое число? ;)

[dragon-ru.livejournal.com]

Решил. Но спойлерить не буду :)

[sleeping-death.livejournal.com]

с мат. решением все понятно :)

[ivan-gandhi.livejournal.com]

f(x)=i*x

(I know, I know)

[spamsink.livejournal.com]

Ух ты, еще жива задачка! Мне ее моя учительница математики задала, когда узнала, что я программированием занимаюсь - благо у нее муж был программист.

f(x) = odd(x) ? x + sgn(x) : -x+sgn(x)

[spamsink.livejournal.com]

Screen at will.

typo

[dizzy57.livejournal.com]

f(f(x) = -x

[http://users.livejournal.com/malfet_/]

Ответ белым по белому:
f(x)=x-(2*x*(x&1))+sgn(x)

[itman.livejournal.com]

Если x - положительное четное число, то функция равна x + 1 или я чего-то не понимаю?

[ttzt.livejournal.com]

min and max := minimum and maximum expressible values

if (0 < x < max/2)
f(x) = max - 7
else if (X > max/2)
f(x) = x - max
else if (mix/2 < x < 0)
f(x) = min - x
else
f(x) = x - min

[deni-ok.livejournal.com]

f(x) = -sign(x) * (abs(x) - 1), если x - четное
f(x) =  sign(x) * (abs(x) + 1), если x - нечетное

[ex-decil.livejournal.com]

function f($x)
{
if ($x>0)
$sign = 1;
else
$sign = -1;

if ($x % 2==0)
return $x+$sign*1;
else
return -($x-$sign*1);
}

Почти то же самое. Правда на ПХП :)

[dimrub.livejournal.com]

Ну например, такая удовлетворяет, вроде бы:

f(x) = { 2x + 1 | x%2 == 0
(1-x)/2 | other }

но думаю, что это не то, что ты имел в виду.

[softmaster.livejournal.com]

не работает %)

[(Anonymous)]

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

Вроде классической задачи - написать функцию, которая 0->1->0
В фольклоре считалось, что хороший с-программист может дать сразу 6 различных короткий решений, отличный - 10

[serezha.livejournal.com]

Есть!
На C# (все эти досадные касты видимо нужны)

private byte MASK1 = 0xAA;
private byte MASK2 = 0x55;

private sbyte f(sbyte x)
{
 if (x >= 0)
  return (sbyte)( x ^MASK1);
 else
  return (sbyte)((sbyte)(x ^ MASK2) + 1);
}

работает, вроде.

[serezha.livejournal.com]

на словах:
что такое -x? (в two's complement)? not и +1.

значит, как это сделать за два вызова?
в первый переворачиваем половину битов, во второй - другую половину, и прибавляем 1 (carry найух).

как отличить первый вызов от второго?
в первый раз бит знака будет 0 (x >= 0), и наоборот.

щорт, только что заметил, что f(f(x))=-x работает только для положительных x.
mea culpa.

думаю дальше.

[http://users.livejournal.com/magister_/]

функция: если аргумент по модулю меньше (2 в максимальной разрядности), то прибавить по модулю (с сохранением знака) максимальную степень двойки;

если больше по модулю (2 в максимальной разрядности), то уменьшить модуль на максимальную степень двойки и поменять знак.

Ну или наоборот (в смысле, на каком этапе знак менять).

Но разве сейчас кто в целых числах программирует?

Upd: кстати, в данной задаче очень удобно, что в целых числах есть +0 и -0.

[http://users.livejournal.com/magister_/]

и еще, кстати:
на ассемблере это сводится к манипуляции с двумя битами: знаковым и старшим (если знаковый бит=1, то сделать =0 и поменять знак, если =0, то сделать =1).

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

[yurilax.livejournal.com]

f(x) = x(-1)^x+1 + sgn(x)

Хотелось бы избавиться от sgn(x) (то есть от любых conditionals), но пока не вижу как (с нулём загвоздка для x/|x| ).

[spamsink.livejournal.com]

sgn(x) на современных компьютерах не требует условных переходов. Необходимый результат достигается с помощью манипуляций с флагом переноса, например:
{carry, x} = x + x
// Теперь бит знака в carry, остальные биты в x
{carry, y} = y - y - carry
// y = размноженный carry
{carry, y} = y - x
// Если x был положительный, и в нем что-то было, то carry = 1, иначе 0
y = x + y + carry
// Результат в y

[(Anonymous)]

Неинтересная функция, но условию задачи удовлетворяет. int32 f(int32 x) { return x > 0 ? -x : x; }

[(Anonymous)]

наврал. не пинайте.

[alexeybobkov]

f(0) = 0

f(1) = 2
f(3) = 4
f(5) = 6
f(7) = 8
...

f(2) = -1
f(4) = -3
f(6) = -5
f(8) = -7
...

f(-1) = -2
f(-3) = -4
f(-5) = -6
f(-7) = -8
...

f(-2) = 1
f(-4) = 3
f(-6) = 5
f(-8) = 7
...

Можно и в общем виде записать, но так, по-моему, понятнее.

Ну, и для 32-битных int ещё есть особый случай :)
f(-2147483648) = -2147483648

[alexeybobkov]

Увы, для 32-битной (и вообще конечнобитной) арифметики - неправильно.
Непонятно, что делать с f(-2147483647).

f(-2147483647) = -2147483648, всё хорошо.
f(2147483647) = ?
2147483648 нельзя, потому что такого числа нет.

По этой же причине, боюсь, у аналогичных решениях в комментах есть та же проблема :(

[zoster-toster.livejournal.com]

f( a) = b;
f( b) = -a;
f(-a) = -b;
f(-b) = a.
таким образом, все ненулевые целые числа разбиваются на классы по 4 элемента.
всего количество целых чисел в 32-битном (и сколько_угодно-битном) представлении не равно 4n+1 => функция нереализуема (хотя существует). точнее будет работать для всех чисел, кроме трех (раз их всего в стандартных целочисленных типах по 4m).
разве нет?

[avva.livejournal.com]

Нет. В 32-битном, например, представлении есть два числа x, для которых -x == x побитово (или, говоря по-другому, операция 2's complement приводит к тем же битам): 0 и еще одно. Число всех оставшихся делится на 4.

[airini.livejournal.com]

f = (x<0)? -x : x;

Хотя не могу не признать, что решение с умножением на i красивее.

[alexeybobkov]

f(f(1)) = 1

[qaraabayna.livejournal.com]

32-битная часть наверное и математикам не будет интересна. Хотя математики - тоже люди, могут с нами в чапаевцев поиграть на клетчатой доске.

[(Anonymous)]

А я такое родил f(x) = -(sqrt(x^2))
f(f(x)) = -(sqrt(-sqrt(x^2))^2) = -x
причем, верно для любых чисел, кроме комплексных. Для комплексных корень четвертой степени и четвертая степень числа.
Только я не особо программер, в 32-х битах особо не шарю :)

[(Anonymous)]

Упс, закосячил :). Для отрицательных не работает.

[softmaster.livejournal.com]

в этой ветке правильное решение:
http://avva.livejournal.com/1863213.html?thread=47500589#t47500589
что в нём не так для 32бит?

[yurilax.livejournal.com]

возьмём 8 бит для простоты: [-128, 127].

f(x) = -sign(x) * (abs(x) - 1), если x - четное
f(x) = sign(x) * (abs(x) + 1), если x - нечетное

f(-127) = 128, но 128 в 2's complement нет и мы overflow в -128
f(-128) = -127 <> 127

[(Anonymous)]

sub get_f {
my $ctr = 0;
sub { my $x = shift; (++$ctr & 1 ? $x : -$x); }
}

$rf = get_f();

[slobin.livejournal.com]

Напоминает мне другую задачку: написать функцию f(x) из действительных чисел в действительные (речь идёт о "настоящих" математических числах, никаких битовых представлений) такую, что f(f(x)) = f^-1(x). Во избежание недоразумений: правая часть -- это не "единица, делённая на", а "функция, обратная к".

Собственно, очень многие рабочие моменты, высказанные в процессе обсуждения Вашей задачи, применимы и здесь -- и очевидность решения для комплексных чисел, и разбиение на четвёрки (здесь тройки). Я даже не считаю это замечание спойлером, потому что до этих мелочей все и так быстро додумаются. Интересно будет дальше. ;-)

... На ашипках учаца ...