7
\$\begingroup\$

Here is MIPS code to return 1 if a number is even, 0 otherwise:

isEven:
  andi $t0, $a0, 1
  li   $t1, 1
  sub  $v0, $t1, $t0
  jr   $ra

My question is whether this can be done in fewer instructions. I could implement isOdd in two instructions (by eliminating the li and sub), but I don't see a single-instruction way to invert just the bottom bit of $t0 into $v0.

\$\endgroup\$
0

1 Answer 1

3
\$\begingroup\$

As was helpfully pointed out by G. Sliepen in a comment, you can flip the bottom bit using xor.

That enables the above code to be rewritten in one fewer instruction:

isEven:
  andi $t0, $a0, 1
  xori $v0, $t0, 1
  jr   $ra

This takes advantages of the properties:

A xor 1 = !A
A xor 0 = A
\$\endgroup\$
3
  • 1
    \$\begingroup\$ sub or add 1 also flips the low bit, and can be done before and. You can do the same 2-instruction trick even on x86 where one of the only copy-and-operate instructions is LEA. A similar question came up on Stack Overflow not long after this: Check if a number is even. \$\endgroup\$ Commented Dec 22, 2020 at 1:26
  • 1
    \$\begingroup\$ MIPS can also implement bitwise NOT with nor $v0, $zero, $a0, so return (~x)&1 also works. Also, don't forget to try asking a compiler for micro-optimization ideas: godbolt.org/z/Trd8TG shows that gcc (and clang) know this trick for MIPS, using andi/xori for return x%2 == 0 for unsigned x. \$\endgroup\$ Commented Dec 22, 2020 at 1:32
  • \$\begingroup\$ @PeterCordes Perhaps both questions were inspired by this tweet: twitter.com/ctrlshifti/status/1288745146759000064?lang=en \$\endgroup\$ Commented Dec 22, 2020 at 20:51

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.