The behavior is built into the chip for all intents and purposes ;-). With that in place, it's just a matter of making the kernel understand what format the binary is in, for example:
Code:
Terry@vectra-$ file /bin/ls
/bin/ls: ELF 32-bit LSB executable, Intel 80386, version 1, for OpenBSD, statically linked, stripped
I'm not sure how the implementations of binutils are done. The software in bintutils basically amounts to an assembler, linker, and associated utilities needed to work with code for the target platform. (You would basically be setting GCC up for cross compile to a different processor.) All of which should be using libraries to handle some of the lower level specifics, such as the GNU Binary File Descriptor and opcodes libraries, I know BFD supports various processors/arches and the exact implementation for a platform is very non-portable stuff; but at the end of the day it's still basically generating code, not running it.
I personally see no reason why you shouldn't be able to compile a 64-bit program on a 32-bit OS, *as long as the necessary tools/libs to manipulate the code can be compiled on the 32-bit box*, it's just the processor won't be able to use the machine code it creates. _Exactly what you can cross compiler from a 32-bit OS_, that I don't know -> I don't do cross compiling; someone else here or on the reliveant mailing lists might be able to help you on the limitations involved.
But doing i386 on AMD64 will be easy.