I've been having this same problem but under a Linux system (32-bit), after searching t'interweb and finding nothing that helped me I went about fixing this issue myself.
I found that if I try to execute certain binaries that are bundled with Android Studio they would not execute, infact both adb and java threw the same error:
java/adb: cannot execute binary file: Exec format error
The fix for java is to use the system jdk not the one bundled with Android Studio.
So I thought what the hell and changed the bundled adb binary.
First thing is to backup the bundled adb:
mv '/path/to/bundled/adb' '/path/to/bundled/adb~'
I then symlinked my system adb to Android Studio's sdk folder:
(your systems adb may be in a different location)
ln -s '/usr/bin/adb' '/path/to/bundled/adb'
And voila it works!
I think it may be due to the binaries being for a 64-bit CPU but I dunno, can anyone confirm this??