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

Question

I recently had a C# technical assessment for a job application where one of the questions was:

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

I'm pretty sure I wasn't allowed to use operators like %, and I couldn't use string conversions or other types. I couldn't think of how to do it other than bit shifting to the left to get the power of 2 (which only solves by powers of 2) or using division by two and the subtraction method (which doesn't help). But it seems like there may be multiple ways to solve the problem.

I ended up submitting without being able to finish the problem and it's been bothering me that I can't find an answer without using a typical but not allowed method. Any ideas?

Answer 1

Deconstructing integers into powers of 2 can be done in various ways. Here is a simple one:

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

Hence you can write

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

This uses only four calls to your allowed functions. Hard to top I believe..