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:
- Look up "bitwise logical operators" in the reference for your favorite programming language, and learn what they do.
- Write a function that outputs a number in binary. For example, print_binary(39) should print "100111". (Obviously, you should not use any binary-formatting feature built in to your programming language or runtime library when solving this problem.)
- Write a function that toggles the two lowest bits of a value. ("Toggle" means to switch to the opposite state: true becomes false and false becomes true.)
- Write a function that rotates the bits in a 8-bit value, shifting all the bits to the right and moving the rightmost bit value to the leftmost position. For example, 10000010 becomes 01000001, and 01000001 becomes 10100000.
- Write a function that swaps the 8-bit halves of a 16-bit value. (And then ask my boss for a job.)
- (Extra credit) Write a function that adds two numbers without using '+' or '-' (or whatever the standard addition/subtraction operators are in your favorite programming language). Here's a hint: 0 + 1 = 1; 1 + 1 = 10; 1 + 1 + 1 = 11. For more extra credit, write a function that multiplies two numbers without using the multiplication operator. Then go outside and look at the sun, you geek.
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 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.
unsigned short original(0xabcd);
unsigned short switched = (original >> 8) + (original << 8);
You'd get objections from some purists for the non-portable assumption that an 'unsigned short' is 16 bits.