5

我最近遇到了这个面试问题，我不擅长位操作。你们能解释一下函数'f'的作用吗？我不确定这个递归函数是做什么的。

unsigned int f (unsigned int a , unsigned int b)
{
   return a ?   f ( (a&b) << 1, a ^b) : b;
}

我试图将代码粘贴到 Visual Studio 中以测试逻辑，但编译器抛出一些错误消息“无法将类型 'uint' 隐式转换为'bool'。返回中的条件语句（a？）是否缺少某些东西？但我”我确定面试问题和上面提到的完全一样

4

2 回答 2

4

已经有几个人在评论中提到这一点只是增加了两个数字。我不确定是否有比尝试一些输入并记录结果更好的方法来解决这个问题。

前任：

f(5,1) --> returns f(2,4) --> returns f(0,6) --> returns 6

 1.) 5&1 = 1 bit shifted = 2:  5^1 = 4
 2.) 2&4 = 0 bit shifted = 0:  2^4 = 6
 3.) a = 0 so return b of 6

f(4,3) --> returns f(0,7) --> returns 7

1.) 4&3 = 0 bit shifted = 0:  4^3 = 7
2.) a = 0 so return b of 7

在展示了几个输出示例之后，我想您可以假设 f 返回两个输入相加。

于 2013-11-01T21:25:43.453 回答
0

未来的雇主要么非常彻底，要么受到残酷和不寻常的惩罚。

对于这个问题的答案，对来自HackersDelight的免费提供的第 2 章的回顾是物超所值的。函数中的加法运算符取自HAKMEM 备忘录——第 23 项，并用左移代替乘以 2。原始的 HAKMEM 备忘录建议：

(A AND B) + (A OR B) = A + B = (A XOR B) + 2 (A AND B)

或用 C 重写：

x + y = (x ^ y) + 2 * (x & y)

然后，创造性的雇主使用(x & y) << 1代替2 * (x & y)和递归来计算求和和or a直到b= a，0此时b返回。

很高兴这不是我的采访。

于 2014-07-02T00:33:40.160 回答