Posts Tagged ‘C’
Dennis M. Ritchie (1941-2011)
During the media storm over the death of Steve Jobs, there was another, arguably more significant, passing: Dennis M. Ritchie, creator of the C programming language and (with long-time colleague Ken Thompson) the Unix operating system, who was found dead at his home in New Jersey on the 12th October after a long illness.
Dennis Ritchie was a computer scientist who truly “helped shape the digital era“: for his work on C and Unix, he was jointly awarded with Thompson in 1983 the ACM Turing Award (see his Turing Award Lecture: “Reflections on Software Research“), as well as the IEEE Richard W. Hamming Medal (1990) and The National Medal of Technology and Innovation (1998) (with the citation describing their contributions as having “led to enormous advances in computer hardware, software, and networking systems and stimulated growth of an entire industry, thereby enhancing American leadership in the Information Age.”). He was the ‘R’ in K&R C and commonly known by his username dmr. Ritchie was the head of Lucent Technologies (formerly Bell Labs, now part of Alcatel-Lucent) System Software Research Department when he retired in 2007.
Ritchie had a key role in shaping today’s computing environment; his influence rivals, if not surpasses, Steve Jobs’ — it is just less visible. While the response from the tech press was excellent, the collective eulogy from the press at large did not quite do justice to Ritchie’s sweeping influence on the modern world. As Rob Pike, Principal Engineer at Google, who spent 20 years working across the hall from Ritchie at Bell Labs, said:
Pretty much everything on the Web uses those two things: C and Unix. The browsers are written in C. The Unix kernel — that pretty much the entire Internet runs on — is written in C. Web servers are written in C, and if they’re not, they’re written in Java or C++, which are C derivatives, or Python or Ruby, which are implemented in C. And all of the network hardware running these programs I can almost guarantee were written in C.
It’s really hard to overstate how much of the modern information economy is built on the work Dennis did.
Much of my research and teaching has been based upon leveraging Ritchie’s work (or its derivatives). Even my undergraduate dissertation developed a GCC front end for BCPL, a precursor to C (see Ritchie’s Development of the C Language). With computer science being a relatively modern discipline, it is a pleasure to be able to meet and hear the early pioneers speak (for example, Donald Knuth at last year’s BCS/IET Turing Lecture); unfortunately, this type of news may start to come all too frequently (such as the sad news in late October of the death of John McCarthy, the father of AI).
But as Brian Kernighan so eloquently puts it:
There’s that line from Newton about standing on the shoulders of giants…we’re all standing on Dennis’ shoulders.
Powers of two
I was looking back through some C code I had written a while ago and found a concise little function for calculating whether an integer is a power of two. In general, there are two main ways to do this: either using its decimal or binary representation. The former approach can be more human-friendly, but generally less efficient; the latter approach is more machine-friendly, but tends to be more efficient. Since integers are stored as binary values in C (precisely how is dependent on the machine architecture), you can see why slicker methods are possible using binary. Essentially: an unsigned integer is a power of two if and only if it has exactly one 1 bit.
int isPowerOfTwo (unsigned int x)
{
return ((x != 0) && !(x & (x - 1)));
}
There are two halves to the expression: x != 0 and !(x & (x – 1)). The first half makes 0 a special case, since the second part of the expression only works correctly for positive numbers. The second half is true when x is a power of two and false when x is not. It turns out that this decrement and compare function is how the power-of-two check is implemented in malloc in the GNU C Library (glibc); let’s see how it works.
Let n be the position of the leftmost 1 bit in x. If x is a power of two, its lone 1 bit is in position n. This means x – 1 has a 0 in position n (recall how binary subtraction works: when subtracting 1 from x, the borrow propagates all the way from position n; bit n becomes 0 and all lower bits become 1). Now, since x has no 1 bits in common with x – 1, x & (x – 1) is 0, and !(x & (x – 1)) is true. Since subtraction borrows from the lowest 1 bit, when x is not a power of two this will be before position n, so it will not propagate. Now x and x – 1 have at least one 1 bit in common (at position n), so x & (x – 1) is non-zero, and !(x & (x – 1)) is false.
Here are some simple 8-bit unsigned integer examples to illustrate:
x |
x - 1 |
x & (x – 1) |
|---|---|---|
00000001 |
00000000 |
00000000 |
00000011 |
00000010 |
00000010 |
00000110 |
00000101 |
00000100 |
00001000 |
00000111 |
00000000 |
00001011 |
00001010 |
00001010 |
10000000 |
01111111 |
00000000 |
11111111 |
11111110 |
11111110 |
You can find more tips and tricks like this in the original HAKMEM (or updated HAKMEMC), as well as the book Hacker’s Delight by Henry S. Warren.
(A big thanks to Rick Regan and his in-depth Ten Ways to Check if an Integer Is a Power Of Two in C blog post)
