Проектирование функции f (f (n)) == -n

Вопрос, который я получил в своем последнем интервью:

Создайте функцию f, такую, что:
f(f(n)) == -n
Где n - 32-разрядное целое число со знаком; вы не можете использовать арифметику сложных чисел.

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

Любые идеи?

Ответы

Ответ 1

Как насчет:

f(n) = sign(n) - (-1)ⁿ * n

В Python:

def f(n): 
    if n == 0: return 0
    if n >= 0:
        if n % 2 == 1: 
            return n + 1
        else: 
            return -1 * (n - 1)
    else:
        if n % 2 == 1:
            return n - 1
        else:
            return -1 * (n + 1)

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

Чтобы заставить его работать для действительных чисел, вам нужно заменить n в (-1) ⁿ на { ceiling(n) if n>0; floor(n) if n<0 }.

В С# (работает для любого двойника, кроме ситуаций переполнения):

static double F(double n)
{
    if (n == 0) return 0;

    if (n < 0)
        return ((long)Math.Ceiling(n) % 2 == 0) ? (n + 1) : (-1 * (n - 1));
    else
        return ((long)Math.Floor(n) % 2 == 0) ? (n - 1) : (-1 * (n + 1));
}

Ответ 2

Вы не сказали, какого языка они ожидали... Вот статическое решение (Haskell). Он в основном вмешивается в два наиболее важных бита:

f :: Int -> Int
f x | (testBit x 30 /= testBit x 31) = negate $ complementBit x 30
    | otherwise = complementBit x 30

Это намного проще в динамическом языке (Python). Просто проверьте, является ли аргумент числом X и возвращает лямбда, которая возвращает -X:

def f(x):
   if isinstance(x,int):
      return (lambda: -x)
   else:
      return x()

Ответ 3

Здесь доказательство того, почему такая функция не может существовать для всех чисел, если она не использует дополнительную информацию (кроме 32 бит int):

Мы должны иметь f (0) = 0. (Доказательство. Пусть f (0) = x. Тогда f (x) = f (f (0)) = -0 = 0. Теперь -x = f ( f (x)) = f (0) = x, что означает, что x = 0.)

Далее, для любых x и y предположим f(x) = y. Тогда мы хотим f(y) = -x. И f(f(y)) = -y => f(-x) = -y. Подводя итог: if f(x) = y, затем f(-x) = -y и f(y) = -x, и f(-y) = x.

Итак, нам нужно разделить все целые числа, кроме 0, на группы из 4, но мы имеем нечетное число таких целых чисел; не только, что, если мы удалим целое число, не имеющее положительного аналога, у нас все еще есть 2 (mod4) числа.

Если мы удалим 2 максимальных числа влево (по значению abs), мы получим функцию:

int sign(int n)
{
    if(n>0)
        return 1;
    else 
        return -1;
}

int f(int n)
{
    if(n==0) return 0;
    switch(abs(n)%2)
    {
        case 1:
             return sign(n)*(abs(n)+1);
        case 0:
             return -sign(n)*(abs(n)-1);
    }
}

Конечно, другой вариант - не соответствовать 0 и получать 2 числа, которые мы удалили в качестве бонуса. (Но это просто глупо, если.)

Ответ 4

Благодаря перегрузке в С++:

double f(int var)
{
 return double(var);
} 

int f(double var)
{
 return -int(var);
}

int main(){
int n(42);
std::cout<<f(f(n));
}

Ответ 5

Или вы можете злоупотреблять препроцессором:

#define f(n) (f##n)
#define ff(n) -n

int main()
{
  int n = -42;
  cout << "f(f(" << n << ")) = " << f(f(n)) << endl;
}

Ответ 6

Это верно для всех отрицательных чисел.

    f(n) = abs(n)

Поскольку есть еще одно отрицательное число, чем положительные числа для целых чисел с двумя дополнениями, f(n) = abs(n) справедливо для еще одного случая, чем f(n) = n > 0 ? -n : n решение, такое же, как f(n) = -abs(n). У вас есть один...: D

UPDATE

Нет, это неверно для одного случая больше, поскольку я только что узнал по litb comment... abs(Int.Min) будет просто переполняться...

Я тоже думал об использовании информации о модуле 2, но пришел к выводу, что она не работает... до раннего. Если все сделано правильно, оно будет работать для всех чисел, кроме Int.Min, потому что это будет переполнение.

UPDATE

Я играл с ним некоторое время, ища хороший хитроумный манипуляционный трюк, но я не мог найти приятный однострочный, в то время как решение mod 2 вписывается в один.

    f(n) = 2n(abs(n) % 2) - n + sgn(n)

В С# это становится следующим:

public static Int32 f(Int32 n)
{
    return 2 * n * (Math.Abs(n) % 2) - n + Math.Sign(n);
}

Чтобы заставить его работать для всех значений, вы должны заменить Math.Abs() на (n > 0) ? +n : -n и включить вычисление в блок unchecked. Затем вы получаете даже Int.Min, сопоставленный с самим собой, поскольку неконтролируемое отрицание делает.

UPDATE

Вдохновленный другим ответом, я собираюсь объяснить, как работает функция и как построить такую функцию.

Давайте начнем с самого начала. Функция f неоднократно применяется к заданному значению n, давая последовательность значений.

    n => f(n) => f(f(n)) => f(f(f(n))) => f(f(f(f(n)))) => ...

Вопрос требует f(f(n)) = -n, то есть двух последовательных приложений f отрицать аргумент. Еще два приложения f - четыре в целом - отрицают аргумент, снова возвращающий n.

    n => f(n) => -n => f(f(f(n))) => n => f(n) => ...

Теперь существует очевидный цикл длины четыре. Подставляя x = f(n) и отмечая, что полученное уравнение f(f(f(n))) = f(f(x)) = -x имеет место, дает следующее.

    n => x => -n => -x => n => ...

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

Одним из многих решений для построения такого цикла является следующее, начиная с n.

 n                 => negate and subtract one
-n - 1 = -(n + 1)  => add one
-n                 => negate and add one
 n + 1             => subtract one
 n

Конкретным примером такого цикла является +1 => -2 => -1 => +2 => +1. Мы почти закончили. Отмечая, что построенный цикл содержит нечетное положительное число, его равномерный преемник и оба числа отрицают, мы можем легко разбить целые числа на многие такие циклы (2^32 кратно четырем) и нашли функцию, удовлетворяющую условиям.

Но у нас есть проблема с нулем. Цикл должен содержать 0 => x => 0, потому что нуль отрицается для себя. А поскольку состояние цикла уже 0 => x следует за 0 => x => 0 => x. Это всего лишь цикл длины два и x превращается в себя после двух приложений, а не в -x. К счастью, есть один случай, который решает проблему. Если x равно нулю, мы получим цикл длины один, содержащий только нуль, и мы решили, что проблема, заключающаяся в том, что нуль является фиксированной точкой f.

Готово? Почти. У нас есть числа 2^32, ноль - неподвижная точка, оставляющая числа 2^32 - 1, и мы должны разбить это число на циклы четырех чисел. Плохо, что 2^32 - 1 не кратно четырем - там останется три числа не в любом цикле длины четыре.

Я объясню оставшуюся часть решения, используя меньший набор 3-битных подписанных itegers от -4 до +3. Мы закончили с нуля. У нас есть один полный цикл +1 => -2 => -1 => +2 => +1. Теперь построим цикл, начинающийся с +3.

    +3 => -4 => -3 => +4 => +3

Возникает проблема, заключающаяся в том, что +4 не представляет собой 3-битное целое число. Мы получили бы +4, отклонив -3 на +3 - то, что по-прежнему является допустимым 3-битным целым числом, - но затем добавив его в +3 (двоичный 011), выдается двоичный код 100. Интерпретируется как целое без знака, это +4, но мы должны интерпретировать его как целое число со знаком -4. Так что на самом деле -4 для этого примера или Int.MinValue в общем случае является второй фиксированной точкой целочисленного арифметического отрицания - 0 и Int.MinValue сопоставлены с ними. Итак, цикл на самом деле выглядит следующим образом.

    +3 =>    -4 => -3 => -4 => -3

Это цикл длины два и дополнительно +3 входит в цикл через -4. В результате -4 корректно отображается себе после двух функциональных приложений, +3 правильно отображается на -3 после двух функциональных приложений, но -3 ошибочно отображается на себя после двух функциональных приложений.

Итак, мы построили функцию, которая работает для всех целых чисел, кроме одного. Мы можем сделать лучше? Нет мы не можем. Зачем? Мы должны построить циклы длины четыре и способны охватить весь целочисленный диапазон до четырех значений. Остальные значения представляют собой две фиксированные точки 0 и Int.MinValue, которые должны отображаться сами по себе и два произвольных целого числа x и -x, которые должны быть сопоставлены друг с другом двумя функциональными приложениями.

Чтобы отобразить x в -x и наоборот, они должны сформировать четыре цикла, и они должны быть расположены в противоположных углах этого цикла. Следовательно, 0 и Int.MinValue должны быть также в противоположных углах. Это правильно отобразит x и -x, но заменит две неподвижные точки 0 и Int.MinValue после двух приложений функций и оставит нас с двумя неудачными входами. Таким образом, невозможно построить функцию, которая работает для всех значений, но у нас есть функция, которая работает для всех значений, кроме одного, и это лучшее, что мы можем достичь.

Ответ 7

Используя комплексные числа, вы можете эффективно разделить задачу отрицания числа на два этапа:

умножьте n на i, и вы получите n * i, который n повернут на 90 ° против часовой стрелки.
снова умножим на i, и вы получите -n

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

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

Я попытался представить это на следующем рисунке, предполагая подписанные 8-битные данные. Вам нужно будет масштабировать его для 32-битных целых чисел. Допустимый диапазон для начального n - от -64 до +63. Здесь, что делает функция для положительных n:

Если n находится в 0..63 (начальный диапазон), вызов функции добавляет 64, отображая n в диапазон 64..127 (промежуточный диапазон)
Если n находится в 64..127 (промежуточный интервал), функция вычитает n из 64, отображая n в диапазон 0... 63

При отрицательном n функция использует промежуточный диапазон -65..- 128.

Ответ 8

Работает за исключением int.MaxValue и int.MinValue

    public static int f(int x)
    {

        if (x == 0) return 0;

        if ((x % 2) != 0)
            return x * -1 + (-1 *x) / (Math.Abs(x));
        else
            return x - x / (Math.Abs(x));
    }

Ответ 9

Вопрос не говорит о том, что тип ввода и возвращаемое значение функции f должны быть (по крайней мере, не так, как вы его представили)...

... просто, когда n является 32-битным целым числом, тогда f(f(n)) = -n

Итак, как насчет чего-то вроде

Int64 f(Int64 n)
{
    return(n > Int32.MaxValue ? 
        -(n - 4L * Int32.MaxValue):
        n + 4L * Int32.MaxValue);
}

Если n - 32-разрядное целое число, то утверждение f(f(n)) == -n будет истинным.

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

Ответ 10

для javascript (или других динамически типизированных языков) вы можете иметь функцию принимать либо int, либо объект и возвращать другую. то есть.

function f(n) {
    if (n.passed) {
        return -n.val;
    } else {
        return {val:n, passed:1};
    }
}

дает

js> f(f(10))  
-10
js> f(f(-10))
10

альтернативно вы можете использовать перегрузку на строго типизированном языке, хотя это может нарушить правила, т.е.

int f(long n) {
    return n;
}

long f(int n) {
    return -n;
}

Ответ 11

В зависимости от вашей платформы некоторые языки позволяют сохранить состояние в функции. VB.Net, например:

Function f(ByVal n As Integer) As Integer
    Static flag As Integer = -1
    flag *= -1

    Return n * flag
End Function

IIRC, С++ допустил это. Я подозреваю, что они ищут другое решение.

Другая идея состоит в том, что, поскольку они не определяли результат первого вызова функции, вы могли использовать нечетную/четность для управления инвертированием знака:

int f(int n)
{
   int sign = n>=0?1:-1;
   if (abs(n)%2 == 0)
      return ((abs(n)+1)*sign * -1;
   else
      return (abs(n)-1)*sign;
}

Добавьте один к величине всех четных чисел, вычтите один из величины всех нечетных чисел. Результат двух вызовов имеет ту же величину, но один вызов, где он даже мы меняем знак. Есть некоторые случаи, когда это не будет работать (-1, max или min int), но оно работает намного лучше, чем что-либо еще предлагаемое до сих пор.

Ответ 12

Использование исключений JavaScript.

function f(n) {
    try {
        return n();
    }
    catch(e) { 
        return function() { return -n; };
    }
}

f(f(0)) => 0

f(f(1)) => -1

Ответ 13

Для всех 32-битных значений (с оговоркой, что -0 - -2147483648)

int rotate(int x)
{
    static const int split = INT_MAX / 2 + 1;
    static const int negativeSplit = INT_MIN / 2 + 1;

    if (x == INT_MAX)
        return INT_MIN;
    if (x == INT_MIN)
        return x + 1;

    if (x >= split)
        return x + 1 - INT_MIN;
    if (x >= 0)
        return INT_MAX - x;
    if (x >= negativeSplit)
        return INT_MIN - x + 1;
    return split -(negativeSplit - x);
}

Вам в основном нужно соединить каждый цикл -x = > x = > -x с y = > -y = > y loop. Поэтому я спаял противоположные стороны split.

например. Для 4-битных целых чисел:

0 => 7 => -8 => -7 => 0
1 => 6 => -1 => -6 => 1
2 => 5 => -2 => -5 => 2
3 => 4 => -3 => -4 => 3

Ответ 14

Версия С++, возможно, несколько сгибающая правила, но работает для всех числовых типов (float, ints, double) и даже типов классов, которые перегружают унарный минус:

template <class T>
struct f_result
{
  T value;
};

template <class T>
f_result <T> f (T n)
{
  f_result <T> result = {n};
  return result;
}

template <class T>
T f (f_result <T> n)
{
  return -n.value;
}

void main (void)
{
  int n = 45;
  cout << "f(f(" << n << ")) = " << f(f(n)) << endl;
  float p = 3.14f;
  cout << "f(f(" << p << ")) = " << f(f(p)) << endl;
}

Ответ 15

x86 asm (стиль AT & T):

; input %edi
; output %eax
; clobbered regs: %ecx, %edx
f:
    testl   %edi, %edi
    je  .zero

    movl    %edi, %eax
    movl    $1, %ecx
    movl    %edi, %edx
    andl    $1, %eax
    addl    %eax, %eax
    subl    %eax, %ecx
    xorl    %eax, %eax
    testl   %edi, %edi
    setg    %al
    shrl    $31, %edx
    subl    %edx, %eax
    imull   %ecx, %eax
    subl    %eax, %edi
    movl    %edi, %eax
    imull   %ecx, %eax
.zero:
    xorl    %eax, %eax
    ret

Проверен код, пройдены все возможные 32-битные целые числа, ошибка с -2147483647 (underflow).

Ответ 16

Использует глобальные... но так?

bool done = false
f(int n)
{
  int out = n;
  if(!done)
  {  
      out = n * -1;
      done = true;
   }
   return out;
}

Ответ 17

Это решение Perl работает для целых чисел, поплавков и строк.

sub f {
    my $n = shift;
    return ref($n) ? -$$n : \$n;
}

Попробуйте некоторые тестовые данные.

print $_, ' ', f(f($_)), "\n" for -2, 0, 1, 1.1, -3.3, 'foo' '-bar';

Вывод:

-2 2
0 0
1 -1
1.1 -1.1
-3.3 3.3
foo -foo
-bar +bar

Ответ 18

Никто никогда не говорил, что f (x) должен быть того же типа.

def f(x):
    if type(x) == list:
        return -x[0]
    return [x]


f(2) => [2]
f(f(2)) => -2

Ответ 19

Я на самом деле не пытаюсь дать решение самой проблемы, но есть несколько комментариев, поскольку вопрос о том, что эта проблема была поставлена, была частью интервью (job?):

Сначала я спрошу: "Зачем нужна такая функция? Какая большая проблема - это часть?" вместо того, чтобы пытаться решить актуальную проблему на месте. Это показывает, как я думаю и как я решаю такие проблемы. Кто знает? Возможно, это и есть фактическая причина, по которой вопрос задается в интервью в первую очередь. Если ответ "Никогда не возражайте, предположите, что это необходимо, и покажите мне, как вы будете проектировать эту функцию". Тогда я продолжу это делать.
Затем я бы написал код сценария С#, который я использовал бы (очевидный: цикл от int.MinValue до int.MaxValue, а для каждого n в этом вызове диапазона f(f(n)) и проверка результата -n), сообщив, что я буду использовать Test Driven Development для доступа к такой функции.
Только если собеседник продолжит просить меня решить поставленную проблему, я действительно начну пытаться писать псевдокод во время самого интервью, чтобы попытаться ответить на какой-то ответ. Тем не менее, я действительно не думаю, что буду прыгать, чтобы взять на себя работу, если интервьюер будет каким-то образом показать, что такое компания...

О, этот ответ предполагает, что интервью было посвящено связанной с программированием позиции на С#. Было бы, конечно, глупым ответом, если бы интервью было связано с математикой.; -)

Ответ 20

Я бы изменил 2 наиболее значимых бита.

00.... => 01.... => 10.....

01.... => 10.... => 11.....

10.... => 11.... => 00.....

11.... => 00.... => 01.....

Как вы можете видеть, это просто добавление, оставляющее бит.

Как я добрался до ответа? Моя первая мысль была просто необходимостью в симметрии. 4 очереди, чтобы вернуться туда, где я начал. Сначала я подумал, что код 2bits Gray. Тогда я подумал, что на самом деле стандартного двоичного кода достаточно.

Ответ 21

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

Умножение на квадратный корень из -1 - это идея, которая только кажется неудачной, потому что -1 не имеет квадратного корня над целыми числами. Но, играя с такой программой, как математика, дает, например, уравнение

(1849436465 ² +1) mod (2 ³² -3) = 0.

и это почти так же хорошо, как наличие квадратного корня из -1. Результатом функции должно быть целое число со знаком. Следовательно, я собираюсь использовать модифицированные modulo-операции mods (x, n), которые возвращают целое число y, сравнимое с x по модулю n, которое ближе всего к 0. Лишь очень немногие языки программирования успешно выполняют модульную операцию, но ее легко определить, Например. в python это:

def mods(x, n):
    y = x % n
    if y > n/2: y-= n
    return y

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

def f(x):
    return mods(x*1849436465, 2**32-3)

Это удовлетворяет f(f(x)) = -x для всех целых чисел в диапазоне [-2 ³¹-2, 2 ³¹-2]. Результаты f(x) также находятся в этом диапазоне, но, конечно, для вычисления потребуются 64-битные целые числа.

Ответ 22

С# для диапазона номеров 2 ^ 32 - 1, все int32-номера, кроме (Int32.MinValue)

    Func<int, int> f = n =>
        n < 0
           ? (n & (1 << 30)) == (1 << 30) ? (n ^ (1 << 30)) : - (n | (1 << 30))
           : (n & (1 << 30)) == (1 << 30) ? -(n ^ (1 << 30)) : (n | (1 << 30));

    Console.WriteLine(f(f(Int32.MinValue + 1))); // -2147483648 + 1
    for (int i = -3; i <= 3  ; i++)
        Console.WriteLine(f(f(i)));
    Console.WriteLine(f(f(Int32.MaxValue))); // 2147483647

печатает:

2147483647
3
2
1
0
-1
-2
-3
-2147483647

Ответ 23

По сути, функция должна делить доступный диапазон на циклы размера 4 с -n на противоположном конце n цикла. Однако 0 должен быть частью цикла размером 1, иначе 0->x->0->x != -x. Из-за того, что 0 один, в нашем диапазоне должно быть 3 других значения (размер которых кратен 4) не в правильном цикле с 4 элементами.

Я выбрал эти дополнительные странные значения MIN_INT, MAX_INT и MIN_INT+1. Кроме того, MIN_INT+1 будет правильно отображаться на MAX_INT, но застрять там и не отображать обратно. Я думаю, что это лучший компромисс, потому что он обладает хорошим свойством только экстремальных значений, которые не работают правильно. Кроме того, это означает, что он будет работать для всех BigInts.

int f(int n):
    if n == 0 or n == MIN_INT or n == MAX_INT: return n
    return ((Math.abs(n) mod 2) * 2 - 1) * n + Math.sign(n)

Ответ 24

Никто не сказал, что он должен быть без гражданства.

int32 f(int32 x) {
    static bool idempotent = false;
    if (!idempotent) {
        idempotent = true;
        return -x;
    } else {
        return x;
    }
}

Обман, но не так много, как много примеров. Еще больше зла - заглянуть в стек, чтобы узнать, является ли ваш адрес вызывающего абонента & f, но это будет более переносимым (хотя не потокобезопасным... поточно-безопасная версия будет использовать TLS). Еще больше зла:

int32 f (int32 x) {
    static int32 answer = -x;
    return answer;
}

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

Ответ 25

Я мог бы предположить использование 31-го бита, поскольку мнимая (i) бит была бы подходом, который поддерживал бы половину всего диапазона.

Ответ 26

работает для n = [0.. 2 ^ 31-1]

int f(int n) {
  if (n & (1 << 31)) // highest bit set?
    return -(n & ~(1 << 31)); // return negative of original n
  else
    return n | (1 << 31); // return n with highest bit set
}

Ответ 27

В этой проблеме указывается "32-разрядные целые числа со знаком", но не указывается, являются ли они twos-complement или ones-supplement.

Если вы используете одно-дополнение, все значения 2 ^ 32 происходят в циклах длины четыре - вам не нужен специальный случай для нуля, и вам также не нужны условные обозначения.

В C:

int32_t f(int32_t x)
{
  return (((x & 0xFFFFU) << 16) | ((x & 0xFFFF0000U) >> 16)) ^ 0xFFFFU;
}

Это работает

Обмен высоким и низким 16-разрядными блоками
Инвертирование одного из блоков

После двух проходов мы побитно инвертируем исходное значение. Который в представлении с одним дополнением эквивалентен отрицанию.

Примеры:

Pass |        x
-----+-------------------
   0 | 00000001      (+1)
   1 | 0001FFFF (+131071)
   2 | FFFFFFFE      (-1)
   3 | FFFE0000 (-131071)
   4 | 00000001      (+1)

Pass |        x
-----+-------------------
   0 | 00000000      (+0)
   1 | 0000FFFF  (+65535)
   2 | FFFFFFFF      (-0)
   3 | FFFF0000  (-65535)
   4 | 00000000      (+0)

Ответ 28

: D

boolean inner = true;

int f(int input) {
   if(inner) {
      inner = false;
      return input;
   } else {
      inner = true;
      return -input;
   }
}

Ответ 29

return x ^ ((x%2) ? 1 : -INT_MAX);

Ответ 30

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

Если я правильно помню, вы отрицаете подписанное 32-битовое целое, просто перевернув первый бит. Например, если n = 1001 1101 1110 1011 1110 0000 1110 1010, то -n = 0001 1101 1110 1011 1110 0000 1110 1010.

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

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

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

Наблюдение. Если вы можете ответить на вышеуказанный вопрос для 32-битного случая, тогда вы также можете ответить за 64-битный случай, 100-битный случай и т.д. Вы просто применяете f к первым 32-разрядным.

Теперь, если вы можете ответить на вопрос для 2-битного случая, Voila!

И да, оказывается, что изменить первые 2 бита достаточно.

Здесь псевдокод

1. take n, which is a signed 32-bit integer.
2. swap the first bit and the second bit.
3. flip the first bit.
4. return the result.

Примечание. Шаг 2 и шаг 3 вместе могут быть выражены как (a, b) → (-b, a). Выглядит знакомо? Это должно напоминать о 90-градусном вращении плоскости и умножении на корень квадрата из -1.

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