我在上次面试中遇到的一个问题是:

设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。

有什么想法吗?


当前回答

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(下溢)。

其他回答

int f(const int n)  {
    static int last_n;

    if (n == 0)
        return 0;
    else if (n == last_n)
        return -n;
    else
    {
        last_n = n;
        return n;
    }
}

哈克,但正确。

事实上,我并没有试图给出问题本身的解决方案,但我有几点意见,因为问题表明,提出这个问题是(工作?)面试的一部分:

我会先问“为什么需要这样的函数?这是什么更大的问题?”而不是试图当场解决实际提出的问题。这表明了我是如何思考和解决这样的问题的。谁知道?这甚至可能是在一次采访中首先提出这个问题的真正原因。如果答案是“没关系,假设它是需要的,并告诉我如何设计这个功能。”我会继续这样做。然后,我将编写我将使用的C#测试用例代码(显而易见:从int.MinValue到int.MaxValue的循环,对于该范围内的每个n调用f(f(n)),并检查结果是-n),告诉我将使用测试驱动开发来获得这样的函数。只有当面试官继续要求我解决所提出的问题时,我才真正开始在面试过程中胡乱写下伪代码,试图得到某种答案。然而,如果面试官能说明公司的情况,我真的不认为我会跳下去接受这份工作。。。

哦,这个答案假设面试是针对一个与C#编程相关的职位。如果面试的是与数学相关的职位,那当然是一个愚蠢的答案

我可以想象,使用第31位作为虚(I)位将是一种支持一半总范围的方法。

我还没有看其他答案,我假设已经彻底讨论了按位技术。

我想我会在C++中想出一些邪恶的东西,希望不会上当受骗:

struct ImplicitlyConvertibleToInt
{
    operator int () const { return 0; }
};

int f(const ImplicitlyConvertibleToInt &) { return 0; }

ImplicitlyConvertibleToInt f(int & n)
{
    n = 0; // The problem specification didn't say n was const
    return ImplicitlyConvertibleToInt();
}

整个ImplicitlyConvertableToInt类型和重载是必需的,因为临时变量不能绑定到非常量引用。

当然,现在来看它,f(n)是否在-n之前执行是不确定的。

对于这种程度的邪恶,也许一个更好的解决方案是:

struct ComparesTrueToInt
{
    ComparesTrueToInt(int) { } // implicit construction from int
};
bool operator == (ComparesTrueToInt, int) const { return true; }

ComparesTrueToInt f(ComparesTrueToInt ct) { return ComparesTrueToInt(); }

C++解决方案;

long long f(int n){return static_cast <long long> (n);}
int f(long long n){return -static_cast <int> (n);}

int n = 777;
assert(f(f(n)) == -n);