尽可能少地使用移位、加法和减法乘以 27

Question

我最近对一份工作申请进行了 C# 技术评估，其中一个问题是：

Question 11: Implement the function int Mult27(int a) such that it returns the result of a multiplied by 27. Do so using only the following functions (provided):
SHL(a,b) shifts all the bits of integer a left by b places.

ADD(a,b) adds two integers giving a+b.

SUB(a, b) subtracts two integers to give a-b.
Do so using as few calls to these functions as possible, assume a is always a positive integer.
public class AnswerEleven
{
    int SHL(int a, int b)
    {
        return a << b;
    }

    int ADD(int a, int b)
    {
        return a + b;
    }

    int SUB(int a, int b)
    {
        return a - b;
    }

    public int Mult27(int a)
    {

    }
}

我很确定我不被允许使用像 % 这样的运算符，而且我不能使用字符串转换或其他类型。除了向左移动位以获得 2 的幂（只能通过 2 的幂求解）或使用除以 2 和减法（无济于事）之外，我想不出该怎么做。但似乎有多种方法可以解决这个问题。

我最终提交但未能完成问题，这一直困扰着我，如果不使用典型但不允许的方法我就找不到答案。有什么想法吗？

Answer 1

这个怎么样：

public int Mult27(int a)
{
    return ADD(ADD(SHL(a, 4), SHL(a, 3)), SUB(SHL(a, 2), a));
}

var ae = new AnswerEleven();
Console.WriteLine(ae.Mult27(1));
Console.WriteLine(ae.Mult27(2));

这给出 27 和 54。

Answer 2

可以通过多种方式将整数分解为 2 的幂。这是一个简单的：

27x = 32x - 5x = 32x - 4x - x

因此你可以这样写

public int Mult27(int a)
{
    return SUB(SUB(SHL(a, 5), SHL(a, 2)), a);
}

这仅使用 4 次调用您允许的函数。我相信很难登顶..

Answer 3

public int Mult27(int a)
{
    a = ADD(a, SHL(a, 1));    // or SUB(SHL(a, 2), a) → a = 3a
    return ADD(a, SHL(a, 3)); // 3a + 8*3a = 27a
}

这有一个很好的属性，它避免在移动 5 时溢出，就像扩展 27x = 32x - 5x

这是一个同样使用 4 次调用的替代版本

int a4 = SHL(a, 2);                 // a4 = a*4
return SUB(SUB(SHL(a4, 3), a4), a); // a4*8 - a4 - a

尽可能少地使用移位、加法和减法乘以 27

Multiply by 27 using only bit shifting, addition and subtraction as few times as possible

c#

bit-manipulation

bit-shift

multiplication