While looking at the ARM instruction set, you notice that the ADD instruction has the so-called "Flexible second operand", which can be abused for quick multiplication. For example, the following instruction multiplies register r1 by 17 (shifting it left by 4 bits and adding to itself):

ADD r1, r1, r1, LSL #4
; LSL means "logical shift left"

The subtraction instruction has that feature too. So multiplication by 15 is also easy to implement:

RSB r1, r1, r1, LSL #4
; RSB means "reverse subtract", i.e. subtract r1 from (r1 << 4)

So this is an excellent optimization opportunity! Certainly, when you write in a C program x *= 15, the compiler will translate that to some inefficient code, while you could replace it by x = (x << 4) - x, and then the compiler will generate better code!

Quickly, you come up with the following cunning plan:

  1. Write a program or a subroutine, in any language, that receives one parameter m, and outputs a C optimizing macro, like the following (for m = 15):

    #define XYZZY15(x) (((x) << 4) - (x))

    or (which is the same)

    #define XYZZY15(x) (-(x) + ((x) << 4))
  2. ???

  3. Profit!


  • The macro's name is essential: magic requires it.
  • Parentheses around x and the whole expression are required: ancient C arcana cannot be taken lightly.
  • You can assume m is between 2 and 65535.
  • The input and output can be passed through function parameters, stdin/stdout or in any other customary way.
  • In C, addition and subtraction have tighter precedence than bit shift <<; use parentheses to clarify order of calculations. More parentheses than necessary is OK.
  • It is absolutely vital that the C expression be optimal, so e.g. x+x+x is not acceptable, because (x<<1)+x is better.
  • Expressions x + x and x << 1 are equivalent, because both require one ARM instruction to calculate. Also, (x << 1) + (x << 2) (multiplication by 6) requires two instructions, and cannot be improved.
  • You are amazed to discover that the compiler detects that (x << 0) is the same as x, so x + (x << 0) is an acceptable expression. However, there is no chance the compiler does any other optimizations on your expression.
  • Even though multiplication by 17 can be implemented in one instruction, multiplication by 17*17 cannot be implemented in two instructions, because there is no C expression to reflect that:

    #define XYZZY289(x) x + (x << 4) + (x + (x << 4) << 4) // 3 operations; optimal

    In other words, the compiler doesn't do common sub-expression elimination. Maybe you will fix that bug in version 2...

This is code-golf: the shortest code wins (but it must be correct, i.e. produce correct and optimal expressions for all m)

Please also give example outputs for m = 2, 10, 100, 14043 and 65535 (there is no requirement on the length of the expression - it can contain extra parentheses, whitespace and shift left by 0 bits, if that makes your code simpler).

  • \$\begingroup\$ For some 2 <= m <= 65535, there will be a worst case value where the number of bitshifts is a maximum. Is it guaranteed that even for this worst case that it will be more efficient to do this many shifts instead of one multiplication? \$\endgroup\$ Mar 23, 2015 at 21:00
  • 1
    \$\begingroup\$ Define “optimal.” I count two operations in both x+x+x and (x<<1)+x. \$\endgroup\$
    – FUZxxl
    Mar 23, 2015 at 21:12
  • 1
    \$\begingroup\$ @FUZxxl: ARM can do as a single instruction x+(y<<k), x-(y<<k), and (y<<k)-x (for registers x,y and any constant k). So there is only one operation in your second example. \$\endgroup\$ Mar 23, 2015 at 21:53
  • 1
    \$\begingroup\$ It's not currently clear to me whether output which uses sub-macros is required or not. Please add a worked example for something like m = 24 where that would make a difference. \$\endgroup\$ Mar 23, 2015 at 22:25
  • 1
    \$\begingroup\$ Does the compiler do common subexpression elimination? If I have ((x<<8)+1)+(((x<<8)+1)<<5), is that 3 ops, or 2? \$\endgroup\$ Mar 24, 2015 at 3:28

2 Answers 2


Python - 414 393 331

This is my entry, which finds the least possible addition/subtraction operations, and subsequently evaluates to a C expression. Not sure it is optimal as multiplication of subexpressions may offer less operations.

import itertools as l
def w(N,s=''):
 for k,v in enumerate(min([t for t in l.product((1,0,-1),repeat=len(bin(N))-1)if sum([v*2**k for k,v in enumerate(t)])==N],key=lambda t:sum(abs(k)for k in t))):
  if v!=0:s+='{:+d}'.format(v)[0];s+='((x)<<{})'.format(k)if k>0 else'(x)'
 return '#define XYZZY{}(x) ({})'.format(N,s.lstrip('+'))

For the cases 2, 10, 100, 14043, 65535:

#define XYZZY2 (((x)<<1))
#define XYZZY10 (((x)<<1)+((x)<<3))
#define XYZZY100 (((x)<<2)+((x)<<5)+((x)<<6))
#define XYZZY14043 (-(x)-((x)<<2)-((x)<<5)-((x)<<8)-((x)<<11)+((x)<<14))
#define XYZZY65535(x) (-(x)+((x)<<16))

The final 65535 took around 11 minutes to compute. Suggestions for improvement (also speedwise) are welcome :-). Thanks to mbomb007 and plg for golfing improvements.

  • 1
    \$\begingroup\$ Change your 2nd line to this: a=lambda t:sum(abs(k)for k in t) to save some bytes. Omit any spaces you can, such as every space before an IF, except where the previous non-whitespace character is a letter. e.g. '+' if -> '+'if and you can do s[0] != '+' else -> s[0]!='+'else \$\endgroup\$
    – mbomb007
    Apr 4, 2015 at 21:32
  • 1
    \$\begingroup\$ This IS code-golf after all. \$\endgroup\$
    – mbomb007
    Apr 4, 2015 at 21:33
  • \$\begingroup\$ The return can be written: return '#define XYZZY{}(x) ({})'.format(N,s.lstrip('+')). And abs(v) > 0 is equivalent to v != 0. Calling sorted on g's current definition can also save a char (also you should make g a generator -- replace the angle brackets with parentheses). Also you can define e=enumerate, and inline a into sorted. \$\endgroup\$
    – ThinkChaos
    Apr 5, 2015 at 8:50
  • \$\begingroup\$ Also you can apply what @mbomb007 said to [...]0 else: [...]0else is fine. \$\endgroup\$
    – ThinkChaos
    Apr 5, 2015 at 8:51
  • \$\begingroup\$ r is unused. L and g can be inlined. Your now inlined g can be written in terms of min instead of sorted()[0]. As r is gone, ` s=''\n` can be added as a param: def w(N,s=''):. After all these changes I'm down to 342, and I'm sure there are other things to do. \$\endgroup\$
    – ThinkChaos
    Apr 5, 2015 at 8:59

Python 508

Slightly more characters than my other answer, but this code runs in roughly one second for all cases 2, 10, 100, 14043, 65535.

def l(n,k=0,o=0):
 while 1:
  if k==0:
   for j in range(1,n):
   for j in range(1,n):
    for u in l(j,k-1,1):
  if o:break 
r=lambda t:sum((1,-1)[k<0]*2**(abs(k)-1)for k in t)
def w(N,s=''):
 g = loop(len(bin(N))) 
 while 1:
  a = g.next()
  if r(a)==N:
   for k in a:
    s+='{:+d}'.format(k)[0];s+='((x)<<{})'.format(abs(k-1)) if abs(k)>1 else'(x)'
   return '#define XYZZY{}(x) ({})'.format(N,s.lstrip('+'))""")

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.