The Mind of a Programmer
Good programmers are good at solving problems because they consider all the dimensions.
A short while ago I published a post about natural born programmers and questioned whether or not they exist. When I was writing it I was thinking about how programmers go about coding solutions to problems that they already know how to solve. I was trying to tap into the mind of a programmer and discover how it thinks. I demonstrated two approaches to solving the simple problem of determining whether a number is odd or even. One solution used a ‘smart’ human approach and the other a ‘simple’ math approach. It generated some good discussions and triggered various reactions. The most interesting one was this one. It discusses my first response to the first comment posted by Matt Turner.
The simple math solution that I suggested was this:
// if divisible by 2 then is even else is odd boolean isEven = number % 2 == 0;
The alternative and bitwise solution that Matt suggested was this:
// if last bit is 0 then is even else is odd boolean isEven = (number & 1) == 0;
I knew that the &1 solution was functionally equivalent to the %2 solution but I wasn’t exactly sure if it was also equally as efficient (or even better). I had to prove it. So I knocked up a quick test program to compare the execution times. When I ran the program I observed that both of them did take the same time to execute. I also analysed the generated bytecode and found that the %2 solution used the IREM bytecode instruction and that the &1 operation used the IAND instruction. My bytecode findings attracted these comments by Michael Speer and Charlie Chan respectively (and other anonymous comments too). Having done a bit of assembler, C, and C++ in my not too old school days, I do have some experience in binary arithmetic and native code optimisation. So I can appreciate the &1 solution. But I never expect to have to apply this knowledge directly to Java programming. I always expect Java to perform all trivial optimisations on my behalf. I should not have to optimise my Java code at this level. I should just write code that expresses what I want in the simplest and clearest way possible.
It has often been said by many programmers that there is no one right solution to a problem. That is definitely the case here. But there is something more interesting here though. If you study the &1 solution you will find that it very closely resembles the ‘smart’ human optimised approach to solving the problem. How? Remember that smart humans can tell whether a number is even or odd just by looking at the last digit. The &1 solution emulates exactly that, yes indeed! The difference is that humans look at the right-most digit whereas machines look at the right-most bit. We have identified a pattern here that is common to both humans and machines. Interesting!
But wait! The %2 approach is a more natural and readable expression of the mathematical definition and is also more easily understood by us humans as adopters of the base 10 decimal number system. It directly expresses at a high level the definition that all even numbers are divisible by two and that all odd numbers are not. At the lower level it expresses it as an IREM bytecode instruction. At the even lower machine code level it expresses it as native assembly instructions. We are now in the world of base 2 binary numbers where operations like ‘divide by two’ involve shifting all bits one place to the right and carrying the right most bit (the remainder). Bits can be checked, set, and toggled with bitwise AND, OR, and XOR operations. At this stage, the %2 instruction is optimised for the machine and more closely resembles the &1 operation. So at the binary level, one can deduce that the %2 operation is essentially equivalent to &1.
By solving problems and comparing solutions we are able to identify common patterns. Gifted programmers are naturally good at it! These are the things we learn and the things that go on in our minds as programmers.