spamsink | Ответ на программистскую задачу

Про три числа

Первоначальное, математичное, решение было у меня такое:

Выберем из трех чисел два (A и B) так, чтобы их четность различалась (это желательно, но если четность всех трех одинакова, то не беда), а у третьего (C) был какой-нибудь бит, однозначно отличающий его от двух остальных.

Без потери общности будем считать, что при x=A должно получаться B, а при x=B - C. Построим "линейную" функцию:

Y = x*(C-B)/(B-A) + (B²-AC)/(B-A)

Вместо целочисленного деления на (B-A) воспользуемся умножением на обратное по модулю 2³². Два числа обратны друг другу, если их произведение равно 1 (у четных чисел обратных нет, но с этим мы разберемся чуть позже). Как же найти обратное к N?
Обратим внимание, что если нечетное число возвести в квадрат, то количество нулей между неизменной единицей в младшем бите и ближайшей старшей единицей увеличивается (действительно, (n*2^k + 1)² = n²*2^2k + n*2^k+1 + 1). Поэтому будем возводить N в квадрат, пока результат не станет равен 1, т.е. пока все лишнее не уедет за пределы разрядной сетки, а потом перемножим все промежуточные результаты, включая первоначальное N. В результате окажется число, которое если [еще раз] умножить на N, то получится 1, т.е. как раз обратное к N.

Если B и A одной четности - будем искать функцию, которая при x = A>>n дает B, а при x=B>>n дает C, где n - такое, что младшие биты A>>n и B>>n различаются. Назначать соответствие между числами и A-B-C, естественно, нужно так, чтобы все уникальные биты C не были в младших n разрядах.

Пока у нас получилось выражение f(x) = (x>>n)*K + M, где f(A) = B, f(B) = C, n - число совпадающих младших бит в A и B.

Теперь осталось лишь скорректировать значение выражения для x=C, не трогая значения при x=A и x=B. Пусть p - номер уникального бита в C, а q - его значение.

Ответ: f(x) + (A - f(C))*((x>>p)&1^(1-q))

Более простое решение, которое мне кажется наиболее прямолинейным, вытекает из того, что найдется как минимум два числа, у которых есть хоть один уникальный бит, поэтому не нужно мучиться с обратным по модулю и с четностями, а всего лишь A+(B-A)*((x>>p_A)&1^(1-q_A)) + (C-A)*((x >> p_B)&1^(1-q_B))

Еще более короткое, но требующее приведения к беззнаковому типу решение дал