Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.
3 replaced http://stackoverflow.com/ with https://stackoverflow.com/
source | link

Another one of the oddities of the x86 instruction set is the multipurpose LEA instructionthe multipurpose LEA instruction, which can do a register-register move, a register-register addition, offsetting by a constant, and scaling all in a single instruction!

Another one of the oddities of the x86 instruction set is the multipurpose LEA instruction, which can do a register-register move, a register-register addition, offsetting by a constant, and scaling all in a single instruction!

Another one of the oddities of the x86 instruction set is the multipurpose LEA instruction, which can do a register-register move, a register-register addition, offsetting by a constant, and scaling all in a single instruction!

2 added 48 characters in body
source | link

Everyone who is attempting this challenge in high-level languages is missing out on the real fun of manipulating raw bits. There are so many subtle variations on ways to do this, it's insane—and a lot of fun to think about. Here'sHere are a few solutions that I devised in 32-bit x86 assembly language.

8B C1     |  mov eax, ecx   ; copy parameter (ECX) to return register (EAX)
          |
F7 D8     |  neg eax        ; two's-complement negation
83 F0 01  |  xor eax, 1     ; XOR last bit to invert odd/even
F7 D8     |  neg eax        ; two's-complement negation
          |
C3        |  ret            ; return from function

Pretty slick; it's hard to see how that can be improved upon. One thing catches my eye, though: those two 2-byte NEG instructions. Frankly, two bytes seems like one byte too many to encode a simple negation, but that's the instruction set we have to work with. Are there any workarounds? Sure! If we XOR by -2, we can replace the second NEGation forwith an INCrement:

8B C1     |  mov eax, ecx
          |
F7 D8     |  neg eax
83 F0 FE  |  xor eax, -2
40        |  inc eax
          |
C3        |  ret

Ready to compileassemble with MASM; call from C as:

Everyone who is attempting this challenge in high-level languages is missing out on the real fun of manipulating raw bits. There are so many subtle variations on ways to do this, it's insane—and a lot of fun to think about. Here's a few solutions that I devised in 32-bit x86 assembly language.

8B C1     |  mov eax, ecx   ; copy parameter (ECX) to return register (EAX)

F7 D8     |  neg eax        ; two's-complement negation
83 F0 01  |  xor eax, 1     ; XOR last bit to invert odd/even
F7 D8     |  neg eax        ; two's-complement negation

C3        |  ret            ; return from function

Pretty slick; it's hard to see how that can be improved upon. One thing catches my eye, though: those two 2-byte NEG instructions. Frankly, two bytes seems like one byte too many to encode a simple negation, but that's the instruction set we have to work with. Are there any workarounds? Sure! If we XOR by -2, we can replace the second NEGation for an INCrement:

8B C1     |  mov eax, ecx

F7 D8     |  neg eax
83 F0 FE  |  xor eax, -2
40        |  inc eax

C3        |  ret

Ready to compile with MASM; call from C as:

Everyone who is attempting this challenge in high-level languages is missing out on the real fun of manipulating raw bits. There are so many subtle variations on ways to do this, it's insane—and a lot of fun to think about. Here are a few solutions that I devised in 32-bit x86 assembly language.

8B C1     |  mov eax, ecx   ; copy parameter (ECX) to return register (EAX)
          |
F7 D8     |  neg eax        ; two's-complement negation
83 F0 01  |  xor eax, 1     ; XOR last bit to invert odd/even
F7 D8     |  neg eax        ; two's-complement negation
          |
C3        |  ret            ; return from function

Pretty slick; it's hard to see how that can be improved upon. One thing catches my eye, though: those two 2-byte NEG instructions. Frankly, two bytes seems like one byte too many to encode a simple negation, but that's the instruction set we have to work with. Are there any workarounds? Sure! If we XOR by -2, we can replace the second NEGation with an INCrement:

8B C1     |  mov eax, ecx
          |
F7 D8     |  neg eax
83 F0 FE  |  xor eax, -2
40        |  inc eax
          |
C3        |  ret

Ready to assemble with MASM; call from C as:

1
source | link

x86 Assembly, 9 bytes (for competing entry)

Everyone who is attempting this challenge in high-level languages is missing out on the real fun of manipulating raw bits. There are so many subtle variations on ways to do this, it's insane—and a lot of fun to think about. Here's a few solutions that I devised in 32-bit x86 assembly language.

I apologize in advance that this isn't the typical code-golf answer. I'm going to ramble a lot about the thought process of iterative optimization (for size). Hopefully that's interesting and educational to a larger audience, but if you're the TL;DR type, I won't be offended if you skip to the end.

The obvious and efficient solution is to test whether the value is odd or even (which can be done efficiently by looking at the least-significant bit), and then select between n+1 or n−1 accordingly. Assuming that the input is passed as a parameter in the ECX register, and the result is returned in the EAX register, we get the following function:

F6 C1 01  |  test  cl, 1                      ; test last bit to see if odd or even
8D 41 01  |  lea   eax, DWORD PTR [ecx + 1]   ; set EAX to n+1 (without clobbering flags)
8D 49 FF  |  lea   ecx, DWORD PTR [ecx - 1]   ; set ECX to n-1 (without clobbering flags)
0F 44 C1  |  cmovz eax, ecx                   ; move in different result if input was even
C3        |  ret

(13 bytes)

But for code-golf purposes, those LEA instructions aren't great, since they take 3 bytes to encode. A simple DECrement of ECX would be much shorter (only one byte), but this affects flags, so we have to be a bit clever in how we arrange the code. We can do the decrement first, and the odd/even test second, but then we have to invert the result of the odd/even test.

Also, we can change the conditional-move instruction to a branch, which may make the code run more slowly (depending on how predictable the branch is—if the input alternates inconsistently between odd and even, a branch will be slower; if there's a pattern, it will be faster), which will save us another byte.

In fact, with this revision, the entire operation can be done in-place, using only a single register. This is great if you're inlining this code somewhere (and chances are, you would be, since it's so short).

    48     |  dec  eax          ; decrement first
    A8 01  |  test al, 1        ; test last bit to see if odd or even
    75 02  |  jnz  InputWasEven ; (decrement means test result is inverted)
    40     |  inc  eax          ; undo the decrement...
    40     |  inc  eax          ; ...and add 1
  InputWasEven:                 ; (two 1-byte INCs are shorter than one 3-byte ADD with 2)

(inlined: 7 bytes; as a function: 10 bytes)

But what if you did want to make it a function? No standard calling convention uses the same register to pass parameters as it does for the return value, so you'd need to add a register-register MOV instruction to the beginning or end of the function. This has virtually no cost in speed, but it does add 2 bytes. (The RET instruction also adds a byte, and there is a some overhead introduced by the need to make and return from a function call, which means this is one example where inlining produces both a speed and size benefit, rather than just being a classic speed-for-space tradeoff.) In all, written as a function, this code bloats to 10 bytes.

What else can we do in 10 bytes? If we care at all about performance (at least, predictable performance), it would be nice to get rid of that branch. Here is a branchless, bit-twiddling solution that is the same size in bytes. The basic premise is simple: we use a bitwise XOR to flip the last bit, converting an odd value into an even one, and vice versa. But there is one niggle—for odd inputs, that gives us n-1, while for even inputs, it gives us n+1— exactly opposite of what we want. So, to fix that, we perform the operation on a negative value, effectively flipping the sign.

8B C1     |  mov eax, ecx   ; copy parameter (ECX) to return register (EAX)

F7 D8     |  neg eax        ; two's-complement negation
83 F0 01  |  xor eax, 1     ; XOR last bit to invert odd/even
F7 D8     |  neg eax        ; two's-complement negation

C3        |  ret            ; return from function

(inlined: 7 bytes; as a function: 10 bytes)

Pretty slick; it's hard to see how that can be improved upon. One thing catches my eye, though: those two 2-byte NEG instructions. Frankly, two bytes seems like one byte too many to encode a simple negation, but that's the instruction set we have to work with. Are there any workarounds? Sure! If we XOR by -2, we can replace the second NEGation for an INCrement:

8B C1     |  mov eax, ecx

F7 D8     |  neg eax
83 F0 FE  |  xor eax, -2
40        |  inc eax

C3        |  ret

(inlined: 6 bytes; as a function: 9 bytes)

Another one of the oddities of the x86 instruction set is the multipurpose LEA instruction, which can do a register-register move, a register-register addition, offsetting by a constant, and scaling all in a single instruction!

8B C1        |  mov eax, ecx
83 E0 01     |  and eax, 1        ; set EAX to 1 if even, or 0 if odd
8D 44 41 FF  |  lea eax, DWORD PTR [ecx + eax*2 - 1]
C3           |  ret

(10 bytes)

The AND instruction is like the TEST instruction we used previously, in that both do a bitwise-AND and set flags accordingly, but AND actually updates the destination operand. The LEA instruction then scales this by 2, adds the original input value, and decrements by 1. If the input value was odd, this subtracts 1 (2×0 − 1 = −1) from it; if the input value was even, this adds 1 (2×1 − 1 = 1) to it.

This is a very fast and efficient way to write the code, since much of the execution can be done in the front-end, but it doesn't buy us much in the way of bytes, since it takes so many to encode a complex LEA instruction. This version also doesn't work as well for inlining purposes, as it requires that the original input value be preserved as an input of the LEA instruction. So with this last optimization attempt, we've actually gone backwards, suggesting it might be time to stop.


Thus, for the final competing entry, we have a 9-byte function that takes the input value in the ECX register (a semi-standard register-based calling convention on 32-bit x86), and returns the result in the EAX register (as with all x86 calling conventions):

           SwapParity PROC
8B C1         mov eax, ecx
F7 D8         neg eax
83 F0 FE      xor eax, -2
40            inc eax
C3            ret
           SwapParity ENDP

Ready to compile with MASM; call from C as:

extern int __fastcall SwapParity(int value);                 // MSVC
extern int __attribute__((fastcall)) SwapParity(int value);  // GNU