Decide if the sum of three numbers is even or odd

Question

Exercise from an Assembly course I'm enrolled into:

Write a program that takes three numbers x,y,z as input, and returns:

• 0 if (x+y+z) is even.

• 1 if (x+y+z) is odd.

(Note that here + means arithmetic addition). Do it without actually adding the numbers. HINT: Use the XOR instruction.

Full exercise-sheet here: GitHub

Here's the code I've written. Please mind the comments I've added for to explain my ideas.

format PE console
entry start

include 'win32a.inc' 

; ===============================================
section '.text' code readable executable

start:

    call    read_hex              ; Provided by the teacher. Reads a hexadecimal number from stdin.
    mov     ebx,    eax
    call    read_hex
    add     ebx,    eax
    call    read_hex
    add     ebx,    eax         

    mov     eax,    ebx           ; Move the sum of the three given numbers into eax.
    xor     eax,    0x1           ; If the number is odd then the lowest bit becomes 0. If the number is even then the lowest bit becomes 1.
    ror     eax,    0x1           ; Rotate the lowest bit out of the register. So that the carry-flag gets a new state.
    jc      evenNumber            ; jc == Jump if the carry-flag has become 1. Means the last bit has been a 1, which in turn means that the number is even.
    mov     eax,    0x1           ; Otherwise just write 0 into eax, which signals an odd number. And prints this to stdout.
    jmp     print_result

evenNumber:
    mov     eax,    0x0

print_result:
    call    print_eax_binary    ; Provided by the teacher. Prints a binary number to stdout.

        ; Exit the process:
    push    0
    call    [ExitProcess]

include 'training.inc'

I'm not completely sure if I have gotten the exercise-task correctly. But let's assume that the entered three numbers have to be summed up and that one has to use xor in some way.

How could I improve my solution? Is there a better solution?

Answer 1

First off, you have nice, clean, well-formatted, easy-to-read code. You have even included comments that explain the goal of each instruction. Too much of the time I review assembly-language code, these are the things that go wrong. You've gotten them all correct. Nice job! Now I don't have to pull my hair out trying to read and understand your code.

Unfortunately, were I your instructor, I'd still have to give you a failing score on the assignment because you didn't follow the rules. The assignment says that you must "Do it without actually adding the numbers.", but right off the bat, you ADD the input values together. And we were off to such a good start… :-(

Now, personally, I think these types of assignments are rather silly, so I wouldn't be giving them. If I wanted you to learn how to use the bitwise operators, I'd find something useful and real-world that they are good for, and then give you that assignment. It's not like I'd have to work very hard. The chip designers didn't put them in merely for fun.

Oh well; you have to do the assignment that you were given. So follow the hint, use XOR. Maybe you don't know exactly what that means, so what I'd do is open up a programmer's calculator (all major desktop operating systems have a "programmer" mode for their calculators) and play around with it. Pick random combinations of positive and negative numbers, and compare what the results are when you add them together versus when you XOR them together. Try to get a feel for what XOR does. Then, look up a formal definition of XOR (exclusive-OR). If you're like me, your eyes glaze over at the symbolic logic stuff (which wasn't so great when I took that course in college); feel free to skip over that for the purposes of this assignment. Your real goal here is to find out what XOR actually does at the bit level. There are lots of detailed explanations of bitwise manipulation online, or you may have a textbook that covers this stuff, too.

For example:

    01101101
XOR 11010100
_____________
    10111001

Notice that each column follows the truth table for an XOR operation, which basically just says that the output is 1 (true) whenever the inputs differ. That's the "exclusive" part of the OR.

Eventually, while doing this preliminary research, I suspect you'd come across someone talking about how XOR operations are used to implement parity checks. Mast's answer here already spilled the beans. Parity indicates whether an integer is even or odd, and can be calculated simply by a XOR sum of the bits. Judging from your comments in the code, you already know that for a binary number, the lowest (least significant) bit determines whether it is odd or even.

So the good news is that your code is almost entirely correct. If you change the ADDs to XORs, it will follow the rules of the assignment and produce the correct result. Thus, you would have:

call    read_hex              ; Provided by the teacher. Reads a hexadecimal number from stdin.
mov     ebx,    eax
call    read_hex
xor     ebx,    eax
call    read_hex
xor     ebx,    eax    

Now we've XOR-summed all of the bits from the three inputs. All that's left is figuring out the parity of the result—i.e., whether the XOR-sum is odd or even.

You've already implemented one way of doing that, but as Quuxplusone pointed out, it is an unnecessarily complicated way. While it doesn't always hold when you start getting into more advanced things, for simple arithmetic operations, fewer instructions means faster code. Arguably more importantly, it means simpler code, which is more likely to be correct code. Moreover, fewer branches virtually always mean faster code, and certainly code whose flow of execution is easier to follow, and thus easier to debug.

I'd disagree slightly with Quuxplusone here and say that clever is totally fine, as long as your cleverness has some notable advantage. You don't always have to write code the "normal" way, because the "normal" way might be sub-optimal. Generally, if we're dropping down to write in assembly, it's because we want to write the best code we possibly can (either fastest, shortest, or whatever metric we are using to judge "best"), which means that "normal" isn't necessarily an important goal. Sometimes, "readable" isn't even an important goal. But, by the same token, I do agree there's no point in deviating from what is normal if your deviation is inferior, and that's certainly the case here.

Your XOR-sum is in the EBX register. You know that the XOR-sum tells you the parity in the least-significant bit. So what is the obvious thing to do? Mask off everything but the least-significant bit, and that'll be your answer! How do we mask off bits? Use a logical AND operation:

and  ebx, 1   ; mask off all but the low-order bit

Oh, and finally, since we need the result in EAX, we'll do:

mov  eax, ebx

(We could have just as easily done the MOV first, before the AND. It doesn't matter.)

Go through your current code, and prove to yourself that this gives exactly the same results, without needing to flip the bit with the XOR, without needing to involve the carry flag (CF) via ROR, and without needing to do any conditional branching (JC).

Putting it all together, the code is essentially:

call    read_hex              ; Provided by the teacher. Reads a hexadecimal number from stdin into EAX.
mov     ebx, eax
call    read_hex
xor     ebx, eax
call    read_hex
xor     ebx, eax         

mov     eax, ebx              ; Move XOR-sum of three given numbers into EAX.
and     eax, 0x1              ; Mask off all but the lowest-order bit.
call    print_eax_binary      ; Provided by the teacher. Prints a binary number in EAX to stdout.

; Exit the process:
push    0
call    [ExitProcess]

Simpler, clearer, faster. Rarely is it possible to say this about any piece of code, but I believe this really is the most optimal way to write this.

Answer 2

The beginning of your program obviously should be following the "HINT" and using xor instead of add.

---

This is some really wacky code:

    ror     eax,    0x1           ; Rotate the lowest bit out of the register. So that the carry-flag gets a new state.
    jc      evenNumber            ; jc == Jump if the carry-flag has become 1. Means the last bit has been a 1, which in turn means that the number is even.
    mov     eax,    0x1           ; Otherwise just write 0 into eax, which signals an odd number. And prints this to stdout.
    jmp     print_result

evenNumber:
    mov     eax,    0x0

print_result:

Typically, if you're just trying to test some bit(s) of a register, you use test, not this wacky ror-and-jc trick. I mean it's clever, but it's not normal — and thus it's not good style. Just do the normal thing, please:

    test    eax, 0x1
    jz      evenNumber

Here, I'll give you a cleverness to make up for the lost ror. The x86 has conditional move instructions, and mov specifically never clears the flags, meaning that you don't need any jumps here:

    test    eax, 0x1
    mov     eax, 0x0   ; set eax to 0...
    cmovz   eax, 0x1   ; ...but immediately set it to 1 *if* the zero flag was set

Or equivalently:

    test    eax, 0x1
    mov     eax, 0x0   ; set the high bytes of eax to 0
    setz    al         ; set the low byte of eax to the value of the zero flag

But best of all:

    andl    eax, 0x1   ; just extract the low-order bit...
    xorl    eax, 0x1   ; ...and flip it

Answer 3

"But let's assume that the entered three numbers have to be summed up and that one has to use xor in some way." Read the instructions again. You're explicitly not allowed to actually sum the numbers. This can be done using XOR as suggested. Your first part of the solution uses add, disqualifying your code.

The keyword to the actual solution would be checking for parity.

Keep in mind you don't have to add the numbers to know whether the result of a sum would be odd or even:

• Odd + odd = even
• Odd + even = odd
• Even + even = even

Whether you do this for 2, 3 or 100 numbers is quite irrelevant, just as the actual value of the result.