Проектная функция f (f (n)) == -n [закрыто]

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

Разработайте функцию f, такую, чтобы:

f(f(n)) == -n

Где n - 32-битный ] целое число со знаком ; Вы не можете использовать арифметику комплексных чисел.

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

Есть идеи?

839
задан 13 revs, 9 users 27% 6 July 2015 в 02:21
поделиться

77 ответов

How about:

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

In 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 automatically promotes integers to arbitrary length longs. In other languages the largest positive integer will overflow, so it will work for all integers except that one.


To make it work for real numbers you need to replace the n in (-1)n with { ceiling(n) if n>0; floor(n) if n<0 }.

In C# (works for any double, except in overflow situations):

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));
}
376
ответ дан 22 November 2019 в 21:11
поделиться

работает для 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
}
10
ответ дан 22 November 2019 в 21:11
поделиться

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

11
ответ дан 22 November 2019 в 21:11
поделиться

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

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, но вы мало что можете с этим поделать, если вам не разрешено возвращать более широкий тип.

12
ответ дан 22 November 2019 в 21:11
поделиться

По сути, функция должна делить доступный диапазон на циклы размера 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)
12
ответ дан 22 November 2019 в 21:11
поделиться

C # для диапазона от 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
13
ответ дан 22 November 2019 в 21:11
поделиться

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

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

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

и для каждого n в этом диапазоне вызовите f (f (n)) и проверьте результат -n ), сказав, что я буду затем использовать Test Driven Development чтобы получить такую ​​функцию.
  • Только если интервьюер продолжит просить меня решить поставленную проблему, я действительно начну пытаться набросать псевдокод во время самого интервью, чтобы попытаться найти какой-то ответ. Тем не менее, я не думаю, что буду прыгать, чтобы устроиться на работу, если интервьюер будет каким-либо признаком того, на что похожа компания ...
  • О, этот ответ предполагает, что интервью было для позиции, связанной с программированием на C #. Конечно, было бы глупым ответом, если бы собеседование проходило по математической позиции. ; -)

    и для каждого n в этом диапазоне вызовите f (f (n)) и проверьте результат -n ), сказав, что я буду затем использовать Test Driven Development чтобы получить такую ​​функцию.
  • Только если интервьюер продолжит просить меня решить поставленную проблему, я действительно начну пытаться набросать псевдокод во время самого интервью, чтобы попытаться найти какой-то ответ. Тем не менее, я не думаю, что буду прыгать, чтобы устроиться на работу, если интервьюер будет каким-либо признаком того, на что похожа компания ...
  • О, этот ответ предполагает, что интервью было для позиции, связанной с программированием на C #. Конечно, было бы глупым ответом, если бы собеседование проходило по математической позиции. ; -)

  • Только если интервьюер продолжит просить меня решить поставленную проблему, я действительно начну пытаться набросать псевдокод во время самого интервью, чтобы попытаться найти какой-то ответ. Тем не менее, я не думаю, что буду прыгать, чтобы устроиться на работу, если интервьюер будет каким-либо признаком того, на что похожа компания ...
  • О, этот ответ предполагает, что интервью было для позиции, связанной с программированием на C #. Конечно, было бы глупым ответом, если бы собеседование проходило по математической позиции. ; -)

  • Только если интервьюер продолжит просить меня решить поставленную проблему, я действительно начну пытаться набросать псевдокод во время самого интервью, чтобы попытаться найти какой-то ответ. Тем не менее, я не думаю, что буду прыгать, чтобы устроиться на работу, если интервьюер будет каким-либо признаком того, на что похожа компания ...
  • О, этот ответ предполагает, что интервью было для позиции, связанной с программированием на C #. Конечно, было бы глупым ответом, если бы собеседование проходило по математической позиции. ; -)

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

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

    16
    ответ дан 22 November 2019 в 21:11
    поделиться

    Uses globals...but so?

    bool done = false
    f(int n)
    {
      int out = n;
      if(!done)
      {  
          out = n * -1;
          done = true;
       }
       return out;
    }
    
    19
    ответ дан 22 November 2019 в 21:11
    поделиться

    :D

    boolean inner = true;
    
    int f(int input) {
       if(inner) {
          inner = false;
          return input;
       } else {
          inner = true;
          return -input;
       }
    }
    
    9
    ответ дан 22 November 2019 в 21:11
    поделиться

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

    \[[^\]*]\]
    

    Или использовать это регулярное выражение для разделения списка скобок (с использованием проверочных утверждений):

    (?<=]|^)\s*,\s*(?=\[|$)
    
    - --------121--------2910575----

    Для всех 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 с циклом ay => -y => y. Таким образом, я спарил противоположные стороны раскола .

    Например, для 4-битных целых чисел:

    0 => 7 => -8 => -7 => 0
    1 => 6 => -1 => -6 => 1
    2 => 5 => -2 => -5 => 2
    3 => 4 => -3 => -4 => 3
    
    21
    ответ дан 22 November 2019 в 21:11
    поделиться

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

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

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

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

    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), но работает намного лучше, чем все, что предлагалось до сих пор.

    46
    ответ дан 22 November 2019 в 21:11
    поделиться

    for javascript (or other dynamically typed languages) you can have the function accept either an int or an object and return the other. i.e.

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

    giving

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

    alternatively you could use overloading in a strongly typed language although that may break the rules ie

    int f(long n) {
        return n;
    }
    
    long f(int n) {
        return -n;
    }
    
    47
    ответ дан 22 November 2019 в 21:11
    поделиться

    The question doesn't say anything about what the input type and return value of the function f have to be (at least not the way you've presented it)...

    ...just that when n is a 32-bit integer then f(f(n)) = -n

    So, how about something like

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

    If n is a 32-bit integer then the statement f(f(n)) == -n will be true.

    Obviously, this approach could be extended to work for an even wider range of numbers...

    48
    ответ дан 22 November 2019 в 21:11
    поделиться

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

    • умножить n на i, и вы получите n * i, то есть счетчик, повернутый на 90 °. -clockwise
    • снова умножить на 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.

    alt text

    96
    ответ дан 22 November 2019 в 21:11
    поделиться

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

        f(n) = abs(n)
    

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

    ОБНОВЛЕНИЕ

    Нет, это не действует для еще одного случая, как я только что узнал по комментарию Литба ... abs (Int.Min) просто переполнение ...

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

    ОБНОВЛЕНИЕ

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

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

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

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

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

    ОБНОВЛЕНИЕ

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

    . Начнем с самого начала. Функция 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                 => 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 не кратно четырем - не останется трех чисел ни в одном цикле длины четыре.

    Я объясню оставшуюся часть решения, используя меньший набор Трехбитные подписанные итераторы в диапазоне от -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 после двух применений функций и оставит нас с двумя ошибочными входами. Поэтому невозможно создать функцию, которая работает для всех значений, но у нас есть такая, которая работает для всех значений, кроме одного, и это лучшее, чего мы можем достичь.

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

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

    103
    ответ дан 22 November 2019 в 21:11
    поделиться

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

    #define f(n) (f##n)
    #define ff(n) -n
    
    int main()
    {
      int n = -42;
      cout << "f(f(" << n << ")) = " << f(f(n)) << endl;
    }
    
    136
    ответ дан 22 November 2019 в 21:11
    поделиться

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

    double f(int var)
    {
     return double(var);
    } 
    
    int f(double var)
    {
     return -int(var);
    }
    
    int main(){
    int n(42);
    std::cout<<f(f(n));
    }
    
    147
    ответ дан 22 November 2019 в 21:11
    поделиться

    Теперь это работает как для XP, так и для Vista. Я создал заглушку winform app с соответствующим кодом (очевидно, его можно очистить, но он передает смысл).

    using System;
    using System.Collections.Generic;
    using System.ComponentModel;
    using System.Data;
    using System.Drawing;
    using System.Linq;
    using System.Text;
    using System.Windows.Forms;
    using System.Runtime.InteropServices;
    
    namespace standbyTest
    {
        public partial class Form1 : Form
        {
    
            [DllImport("Kernel32.DLL", CharSet = CharSet.Auto, SetLastError = true)]
            protected static extern EXECUTION_STATE SetThreadExecutionState(EXECUTION_STATE state);
    
            [Flags]
            public enum EXECUTION_STATE : uint
            {
                ES_CONTINUOUS = 0x80000000,
                ES_DISPLAY_REQUIRED = 2,
                ES_SYSTEM_REQUIRED = 1,
                ES_AWAYMODE_REQUIRED = 0x00000040
            }
    
            public Form1()
            {
                if(Environment.OSVersion.Version.Major > 5)
                {
                    // vista and above: block suspend mode
                    SetThreadExecutionState(EXECUTION_STATE.ES_AWAYMODE_REQUIRED | EXECUTION_STATE.ES_SYSTEM_REQUIRED | EXECUTION_STATE.ES_CONTINUOUS);
                }
    
                InitializeComponent();
    
                //MessageBox.Show(string.Format("version: {0}", Environment.OSVersion.Version.Major.ToString() ));
    
            }
    
            protected override void OnClosed(EventArgs e)
            {
                base.OnClosed(e);
    
                if(Environment.OSVersion.Version.Major > 5)
                {
                    // Re-allow suspend mode
                    SetThreadExecutionState(EXECUTION_STATE.ES_CONTINUOUS);
                }
            }
    
    
            protected override void WndProc(ref System.Windows.Forms.Message m)
            {
                // Power status event triggered
                if(m.Msg == (int)WindowMessage.WM_POWERBROADCAST)
                {
                    // Machine is trying to enter suspended state
                    if(m.WParam.ToInt32() == (int)WindowMessage.PBT_APMQUERYSUSPEND ||
                            m.WParam.ToInt32() == (int)WindowMessage.PBT_APMQUERYSTANDBY)
                    {
                        // Have perms to deny this message?
                        if((m.LParam.ToInt32() & 0x1) != 0)
                        {
                            // If so, deny broadcast message
                            m.Result = new IntPtr((int)WindowMessage.BROADCAST_QUERY_DENY);
                        }
                    }
                    return;
                }
    
                base.WndProc(ref m);
            }
        }
    
    
    
        internal enum WindowMessage
        {
    
            /// <summary>
            /// Notify that machine power state is changing
            /// </summary>
            WM_POWERBROADCAST = 0x218,
            /// <summary>
            /// Message indicating that machine is trying to enter suspended state
            /// </summary>
            PBT_APMQUERYSUSPEND = 0x0,
            PBT_APMQUERYSTANDBY = 0x0001,
    
            /// <summary>
            /// Message to deny broadcast query
            /// </summary>
            BROADCAST_QUERY_DENY = 0x424D5144
    
    
        }
    }
    
    ---------121--------4461390--- -

    Вы не сказали, какой язык они ожидали ... Вот статичное решение (Хаскелл). Это в основном мешает 2 наиболее значимым битам:

    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()
    
    439
    ответ дан 22 November 2019 в 21:11
    поделиться

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

    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;
    }
    
    21
    ответ дан 22 November 2019 в 21:11
    поделиться
    return x ^ ((x%2) ? 1 : -INT_MAX);
    
    9
    ответ дан 22 November 2019 в 21:11
    поделиться

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

    Если я правильно помню, вы отрицаете 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-битного случая, вуаля!

    И да, оказывается, что достаточно заменить первые 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.

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

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

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

    И да, оказывается, что достаточно изменить первые 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, б) -> (-б, а). Выглядит знакомо? Это должно напомнить вам о повороте плоскости на 90 градусов и умножении на квадратный корень из -1.

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

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

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

    И да, оказывается, что достаточно изменить первые 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, б) -> (-б, а). Выглядит знакомо? Это должно напомнить вам о повороте плоскости на 90 градусов и умножении на квадратный корень из -1.

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

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

    И да, оказывается, что достаточно изменить первые 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.

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

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

    И да, оказывается, что достаточно изменить первые 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.

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

    Выглядит знакомо? Это должно напомнить вам о повороте плоскости на 90 градусов и умножении на квадратный корень из -1.

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

    Выглядит знакомо? Это должно напомнить вам о повороте плоскости на 90 градусов и умножении на квадратный корень из -1.

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

    7
    ответ дан 22 November 2019 в 21:11
    поделиться

    В задаче указано «32-разрядные целые числа со знаком», но не указано, являются ли они дополнением до двух или дополнением до единицы .

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

    В C:

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

    Это работает по принципу

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

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

    Примеры:

    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)
    
    10
    ответ дан 22 November 2019 в 21:11
    поделиться

    Here's a proof of why such a function can't exist, for all numbers, if it doesn't use extra information(except 32bits of int):

    We must have f(0) = 0. (Proof: Suppose f(0) = x. Then f(x) = f(f(0)) = -0 = 0. Now, -x = f(f(x)) = f(0) = x, which means that x = 0.)

    Further, for any x and y, suppose f(x) = y. We want f(y) = -x then. And f(f(y)) = -y => f(-x) = -y. To summarize: if f(x) = y, then f(-x) = -y, and f(y) = -x, and f(-y) = x.

    So, we need to divide all integers except 0 into sets of 4, but we have an odd number of such integers; not only that, if we remove the integer that doesn't have a positive counterpart, we still have 2(mod4) numbers.

    If we remove the 2 maximal numbers left (by abs value), we can get the function:

    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);
        }
    }   
    

    Of course another option, is to not comply for 0, and get the 2 numbers we removed as a bonus. (But that's just a silly if.)

    284
    ответ дан 22 November 2019 в 21:11
    поделиться

    Я бы хотел изменить 2 старших бита.

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

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

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

    16
    ответ дан 22 November 2019 в 21:11
    поделиться

    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 (недостаточное заполнение).

    20
    ответ дан 22 November 2019 в 21:11
    поделиться

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

    def f(x):
        if type(x) == list:
            return -x[0]
        return [x]
    
    
    f(2) => [2]
    f(f(2)) => -2
    
    18
    ответ дан 22 November 2019 в 21:11
    поделиться

    Это решение 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
    
    19
    ответ дан 22 November 2019 в 21:11
    поделиться

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

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

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

    почти так же хорошо, как квадратный корень из -1. Результатом функции должно быть целое число со знаком. Следовательно, я собираюсь использовать модифицированные операции по модулю 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 31 -2, 2 31 -2] . Результаты f (x) также находятся в этом диапазоне, но, конечно, для вычисления потребуются 64-битные целые числа.

    16
    ответ дан 22 November 2019 в 21:11
    поделиться

    В PHP

    function f($n) {
        if(is_int($n)) {
            return (string)$n;
        }
        else {
            return (int)$n * (-1);
        }
    }

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

    Изюминкой этого решения является то, что оно работает независимо от того, начинаете ли вы со строки или целого числа, и ничего не меняет при возврате f (n).

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

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

    Изюминкой этого решения является то, что оно работает независимо от того, начинаете ли вы со строки или целого числа, и ничего не меняет при возврате f (n).

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

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

    Изюминкой этого решения является то, что оно работает независимо от того, начинаете ли вы со строки или целого числа, и ничего не меняет при возврате f (n).

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

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

    Изюминкой этого решения является то, что оно работает независимо от того, начинаете ли вы со строки или целого числа, и ничего не меняет при возврате f (n).

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

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

    Изюминкой этого решения является то, что оно работает независимо от того, начинаете ли вы со строки или целого числа, и ничего не меняет при возврате f (n).

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

    6
    ответ дан 22 November 2019 в 21:11
    поделиться

    как насчет этого (язык C):

    int f(int n)
    {
        static int t = 1;
        return (t = t ? 0 : 1) ? -n : n;
    }
    

    только что попробовал, и

    f(f(1000)) 
    

    возвращает -1000

    f(f(-1000)) 
    

    возвращает 1000

    это правильно или я упускаю точку?

    1
    ответ дан 22 November 2019 в 21:11
    поделиться
    Другие вопросы по тегам:

    Похожие вопросы: