warpedjavaguy

Imperative by day and functional by night

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.

Advertisements

Written by warpedjavaguy

January 18, 2008 at 11:41 am

Posted in java, programming

Tagged with

10 Responses

Subscribe to comments with RSS.

  1. enjoyed reading it

    Ankur

    January 19, 2008 at 12:36 am

  2. Nice one

    Ramesh

    January 19, 2008 at 2:03 am

  3. I like beans

    Ervin Sholpnick

    January 19, 2008 at 3:26 am

  4. It is funny how I never noticed the resemblance between the way humans determine even and odd numbers (by looking at the right-most digit), and the way computers can do the same task (by looking at the right-most bit). That was a very interesting observation, and I am sure it can be extended to many other situations as well.

    Amr El-Helw

    January 19, 2008 at 7:14 am

  5. wow, that’s very interesting.

    వికటకవి

    January 19, 2008 at 7:21 am

  6. Hi Guys nice article, if you like this series you shold read “The C Language” by K&R a real masterpice book of programming. (They invented the language used to create Unix, Solaris, Windows NT and many more well known apps.)
    C and C++ (I love them) gave us a window into the “machine’s mind”, but we end up creating thousands and even millons of lines of code. The same effect is happenning today with Java.
    My Question after many years is “why we still thinking in procedures” when OOP gives us a fantastic freedom to think at a higher level.
    In my experience SmallTalk and Ruby are the closest thing to the concept of using objects by manipulation.
    Please let me explain: when I use my ipod I don’t think on how will it work, I just press the buttons and learn to use it as I go.
    When I lernt SmallTalk using lists and Dictionaries was just that!, the VMC model, not a big deal and by that time I looked into large systems and they where working just fine!
    Petty ST din’t have the sponsorship of the commercial products we “need” to use for commercial projects. (IBM let them down)
    Bit and Bytes have no political side but we humans have.
    I am reading now about parallel programming on the Intel series and I’m glad some of the gurus after many years convey to simplify and think in simple terms will make it simple at the end.
    Comparing bits was fantastic technic when we had 4 and 8 bits word processor power and just 16MBytes of storage to work with. I like the article discution on operators, bit logic gates ans so, for compiler optimization but don’t feel is appropiated for programmer to increase productivity.
    Java programmers you have the power to go beyond the fundation and create something that simplifies the concepts and programming using the fundation. This is your call.

    Luis

    January 22, 2008 at 10:09 pm

  7. hi there!! programmers think well and they are broad minded. if they don’t have that skills, then they will not be a good programmer.programmers should think deeply in solving a problem. it’s not that easy to think that way, that is why i am so amaze on programmers and i really admire their skills. they are given by God a special talent that is so amazing. it’s not that easy too to be a programmer. in programming also, there are a lot of characteristics that be developed. one of this is your patience. so, keep up the good works guys.. you really have a special talent. so, make the most out of it. (lol….) have a nice day to you!!

    system develpment

    April 29, 2008 at 1:43 pm

  8. hi… it’s a good article. i agree on what you have said that programmers think well. they will not be able to solve a certain problem if the don,t think deeply. they are so lucky of having that kind of talent from God. programmers are really good in solving. i admire those who has the talent in programming because not all has the capability to solve. have a great day!!

    system develpment

    April 29, 2008 at 1:50 pm

  9. as a programmer, I say we think backwards…at least thats what I do. Before I start coding I think of what the out put would be….before I write an algorithm or mathematical expression….I think of the output first hence why Matt Turner’s comment was // if last bit is 0 then is even else is odd. This also as we all know has to do with how binary. After programming for so long we begin to think of the output first and the root.

    Allen

    December 18, 2011 at 11:28 am


Comments are closed.

%d bloggers like this: