Friday, October 07, 2005


Bits and Bytes

A bit is the fundamental unit of information in digital computers. It can be in one of two states, usually thought of as on/off, true/false, 1/0, or set/clear. By combining multiple bits, one can distinguish between a lot of states. For example, if you put eight bits together into a byte, the number of distinguishable states is 2 to the eighth power, or 256. If you put two bytes together into a word, then the number of distinguishable states provided by those 16 bits is 256 squared, or 65,536.

It is often useful to think of the states as integer numbers. The 256 states in a byte can be mapped to the numbers 0-255, or if you need signed arithmetic, they can be mapped to the range from -127 to +128. By combining bytes, one can get larger ranges of integers, and by combining one integer value with an integer divisor, exponent or other modifiers, one can represent fractions, decimal numbers, complex numbers, or any other kind of number.

This is the basic underpinning of all data representation in a computer. I wish I could say that the above paragraphs are a simplified layman's explanation, but surprisingly, lots of professional computer programmers don't understand it.

One of my boss's favorite interviewing exercises is to ask the candidate to write a function that swaps the two halves of a 16-bit value. For example, the function should change 1111111100000000 to 0000000011111111, or change 1010101000000000 to 0000000010101010. Trust me, this is an elementary problem, and the simplest most-straightforward implementation takes about three lines of code. Over 90% of candidates can't do it. I don't mean that 90% come close but fail some sort of tricky borderline case; I mean that 90% stare at the whiteboard for a few minutes, maybe doodle a little bit, and then just give up. Even after being reminded of the programming-language operators that manipulate bits, 90% are still totally lost.

Yesterday, one candidate answered the question by saying "I don't think I belong in your group. Thank you for your time," and then he left.

Because of the high failure rate on the above question and our desperate need to find anybody to work for us, the boss has started asking simpler questions, like "Please write the numbers from 0 to 15 in binary." Again, for someone applying for an embedded-systems programming job, this should be trivial. The candidates are generally more successful at this, but there is still a surprising amount of cluelessness. The boss wanted to ask one of the candidates to leave her Ph.D. on the desk on her way out.

It really does boggle my mind. I understand that a lot of programmers consider bits and bytes to be low-level implementation details that should be hidden beneath higher-level abstractions, and programmers who have exclusively worked with higher-level languages may not have much experience with the low level. But why are they applying for C++ embedded-systems jobs if they don't know this stuff? How can someone have 10 years of programming experience, and not know how to toggle a bit?

In my mind, it's akin to a mathematician not knowing how to do addition, or a chemist not knowing the properties of hydrogen. I suppose my background is a little atypical, in that I started with low-level assembly-language programming as a kid and moved up into higher-level languages later, whereas most programmers start with the high-level stuff and remember their one-semester assembly-language course with dread. If one's career consists exclusively of reading data from a database and displaying it on a web page, one may not have ever needed to worry about the individual bits. But still, a programmer who can't make sense out of a hex dump or who doesn't understand why a value of -1 might magically change to 65,535 really needs some remedial training.

If you are a programmer (or want to be one) and you react to this by saying "Geez, I have no idea how to do that stuff either", I'd recommend the following exercises:

If your boss can arrange a visa for me, I promise to answer all his bit-fiddling questions any day :)
I have a semi-related rant on the subject of deal breaker interview questions... I was ask that one.. or something similar to it on an interview for a sysadmin job.. nevermind the most complicated programming would have involved shell script or some php... Lots of people it seems.. have these little pet questions they like to ask.. I just get annoyed when they attach meaning to it when the question is really unrelated to the job. I know that's not the case here.. but I'm sure you have run into this too at some point.

If an interviewer goes off asking me things that are barely related to the job.. and not anything that I've claimed to have a background in.. it usually comes off as them trying to be superior... or working off a script with little idea what they are doing. =]
I just started playing with a basic stamp... trying to build a PCL switch for my home airport... these things are neat. I might try to make a better beacon after this if it goes well.. something with high intensity leds that strobe in very visible patterns. Ever worked with these?
I've had stupid interview questions. At one potential employer, I did very well when interviewing with the technical people, then I had to interview with the manager. He liked asking those supposedly creative thinking-outside-the-box questions, like "How would you figure out how many gas stations a town needs?" I decided at that moment that I wasn't interested in the job, and made no effort to hide it.

I haven't played with a Basic Stamp, but have messed around with PIC microcontrollers. I created a little 7-segment LED controller program, which was kinda fun. I'd like to do some "real" embedded-systems programming, but at my current job, that just means Windows XP Embedded, which isn't much different from desktop application development.
I mostly do desktop applications, but I'll take a stab at it:

unsigned short original(0xabcd);
unsigned short switched = (original >> 8) + (original << 8);
Yep, that'll work. I'd use the '|' (or) operator instead of '+', but the result is the same.

You'd get objections from some purists for the non-portable assumption that an 'unsigned short' is 16 bits.
Post a Comment

<< Home

This page is powered by Blogger. Isn't yours?