# Branchless (MIPS) assembly code for median of 3

I was trying to write a short MIPS32 code for computing the median of three registers.

The rules:

• Assume that some values are pre-loaded into $t0, $t1, $t2. • The median of the three values should be placed in $t0.
• No branches are allowed, but otherwise any instruction is okay.
• You may arbitrarily modify the values of all registers.

I was able to optimize it down to 15 instructions. Can you do better?

• Welcome to Code Golf! I added the code-golf tag, but other than that this challenge looks good. (You might still want to check out the sandbox for future challenges, it can be pretty useful sometimes) Commented Nov 2, 2021 at 16:59
• @RedwolfProgrammed - thanks!
– M A
Commented Nov 2, 2021 at 17:00
• I've retagged this as atomic-code-golf since the count seems to be the number of instructions, although this could be made more clear in the body of the challenge. Commented Nov 2, 2021 at 20:08
• May I modify some specific addresses in memory? May I use jump instructions j/jal/jr? May I modify the code during execution? Commented Nov 3, 2021 at 0:45
• @Bubbler - anything is allowed except branches.
– M A
Commented Nov 4, 2021 at 9:49

# 7 instructions

slt $t3,$t0, $t1 slt$t4, $t2,$t1
slt $t5,$t2, $t0  Compare all three pairs of values. xor$t3, $t3,$t4
movn $t0,$t1, $t3  $t1 is the median if it is greater than exactly one of the other values.

xor $t5,$t5, $t4 movn$t0, $t2,$t5


$t2 is the median if it is less than exactly one of the other values. (Otherwise, $t0 is already the median.)

• Very nice. I followed the same logic, but my implementation required more than twice the number of instructions :).
– M A
Commented Nov 4, 2021 at 8:40

# 8 instructions

slt $t4,$t2, $t1 movn$t3, $t1,$t4
movn $t1,$t2, $t4 movn$t2, $t3,$t4


Rearrange $t1 and $t2 so that $t1$t2.

slt $t3,$t2, $t0 slt$t4, $t0,$t1
movn $t0,$t2, $t3 movn$t0, $t1,$t4


If $t0 falls between $t1 and \$t2, it is already the median. If it's outside that range, the one it lies beyond is the median.