компьютерщики

[juan_gandhi]

Вчера между делом помянул задачку - для int32 найти функцию f, чтобы f(f(x)) = -x

Один взялся. Сегодня за завтраком говорит мне: я понял, в чем дело. -x - не функция. Нет такой функции.

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

P.S. Куда я попал.

Comments

А вы говорите логика

[andybil.livejournal.com]

Он же не видел.

[elexandra.livejournal.com]

ферма им

[juan-gandhi.livejournal.com]

Да уж

[anonim-legion.livejournal.com]

А ответ у задачки какой?

[juan-gandhi.livejournal.com]

Ответ хороший, но я не хотел бы так сразу раскрывать.

[blackyblack.livejournal.com]

f(x) -> if(x > 0) return (-x);

[juan-gandhi.livejournal.com]

Это что за текст? Я не понял.

[sassa-nf.livejournal.com]

ну и вот, подайте -1 на вход

[soonts.livejournal.com]

Мне кажется он прав, -x правда не функция для int32.
Потому что INT_MIN влезает в int32, а -INT_MIN нет.

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

[juan-gandhi.livejournal.com]

1. нет
2. ну и какие же?

[dvulis.livejournal.com]

yawn http://gurmeet.net/puzzles/ffx-x/

или f(x)=i x, где i = sqrt(-1).

[elexandra.livejournal.com]

ага, я эту ссылку тоже нагуглил

а про i не догадался, хоть и не int32

[deni-ok.livejournal.com]

Бгг. Каждый год!

[juan-gandhi.livejournal.com]

Ну, в этот раз ответы более необычные, чем в прошлый год.

[imfromjasenevo.livejournal.com]

тут уже написали, что комплексные числа надо вводить
можно ли считать ответом, что-то типа f=i*x, где x=(а b), а i={{0 -1},{1 0}}, [а]=[b]=16bit

[juan-gandhi.livejournal.com]

Try again. f(f(x)).

[snsokolov.livejournal.com]

def f(x):
return (2<<32) + (x if abs(x) <= (1<<32) else -x)

All tests passed:
self.assertEqual(f(f(0)), -0)
self.assertEqual(f(f(1)), -1)
self.assertEqual(f(f(-(1<<31))), (1<<31))
self.assertEqual(f(f((1<<31)-1)), -(1<<31)+1)

[dvulis.livejournal.com]

а если в этом компьютере не two's complement, a one's complement?

[huzhepidarasa.livejournal.com]

если f(0)=f0!=0, то f(f0)=0 и f(f(f0))=f0!=-f0. противоречие. значит, f(0)=0.

если x!=0, то f(x)!=0 (иначе f(f(x))=0), и f(x)!=x (иначе f(f(x))=x).

положим f(x)=y, тогда f(y)=-x, f(-x)=-y, f(-y)=x.

итого, f разбивает все ненулевые целые числа на циклы из четырех. таких функций много. например, набор циклов {(1,2,-1,-2), (3,4,-3,-4), (5,6,-5,-6), ...} задает такую функцию на целых числах.

но для 32-битных чисел такой функции нет, потому что число таких чисел (без нуля) не делится на 4.

[elexandra.livejournal.com]

спасибо, хуже пидараса

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

[huzhepidarasa.livejournal.com]

Херня-война, лучше вот решите задачку для детей из Арнольда. Сегодня прилив достиг высшей точки в полдень, когда это произойдет в следующий раз (в этом же месте)?

(Мое пояснение: в такие подробности, как наличие континентов на Земле и Солнца в небе, вдаваться не надо; точность ответа по возможности в пределах 5 минут).

[anonim-legion.livejournal.com]

Через месяц в это же время.

Не могу не вспомнить классику

[anonim-legion.livejournal.com]

Шанкр вместе с гонореей
Тоже выдумал еврей
Только зачем? Вот непонятно...
Монады, монады, кругом одни монады!

[ermouth.livejournal.com]

Придётся хранить в этих 32 битах вектор. f должна поворачивать вектор на четверть оборота, значит нам надо хотя бы 2 бита, чтобы хранить число поворотов на пипополам. Остаётся 30 бит на «длину» вектора, а один из 2 бит счётчика поворотов и будет знáком. Второй бит будет показывать, лежит текущее состояние на вещественной оси или проекция на эту ось равна нулю.

[rrr2.livejournal.com]

Функция поворота на 90 градусов в комплексной плоскости

[monmarth.livejournal.com]

Идеально нельзя, конечно.
Но в первом приближении как-то так:

int f(int x)
{
if(x == -1) return 1<<31;
if(x == 1<<31) return 1;
if(x == 1 || x == 0) return x-1;


if(x < 0)
return x&1 ? x+1 : 1-x ;
else
return x&1 ? x-1 : -1-x ;
}

[juan-gandhi.livejournal.com]

Я чувствую, вам нужен кюей, чтобы опровергнуть, сами не можете?

[exceeder.livejournal.com]

навскидку, не читая комментариев
-abs(x)
но может, это слишком просто и там есть ограничения на такое?
То есть, почему сомнения, это при чем тут int32? Ну есть одно число, которое не отминусуется. Так оно всегда есть.

[juan-gandhi.livejournal.com]

-abs(-abs(-5)) != 5

[exceeder.livejournal.com]

навскидку, не читая комментариев
-abs(x)
но может, это слишком просто и там есть ограничения на такое?
То есть, почему сомнения, это при чем тут int32? Ну есть одно число, которое не отминусуется. Так оно всегда есть.

[lev shubnikov (from livejournal.com)]

Int8:

0 --> 0
1 --> 2 --> -1 --> -2 --> 1
3 --> 4 --> -3 --> -4 --> 3
...
125 --> 126 --> -125 --> -126 --> 125

127, -127, 80h explodes the Earth

[smirnfil.livejournal.com]

Вопрос - Оно должно на всем int32 быть определено? Тогда вопрос чему у вас равен -(LONG_MIN)? В С# два контекста - в одном случае вылет. То есть такой функции действительно не будет, поскольку -х не определен на int32. В другом -(LONG_MIN) = LONG_MIN.

Но все равно такой функции не будет - будут две неподвижных точки (0 и LONG_MIN) если x = -x, то f(x) = x. а все остальное должно делится на четверки так как f(f(f(f(x)))) = x, а оно не делится.

[juan-gandhi.livejournal.com]

-(LONG_MIN) = LONG_MIN, наверно. У вас с этим проблемы?

Идея, что 0-x определен не на всех x, конечно, свежа.

А дальше да, ответ правильный. :)

[vyakunin.livejournal.com]

x + (1 << 30)

[monmarth.livejournal.com]

если бы целые хранились в прямом (а не дополнительном) коде, это было бы не только красиво, но и верно. :)