Tag Archives: Reblogged

Coining the word “software”

softwaredefn

Computing pioneer Paul Niquette’s memoir begins with the tale of how he came to coin the term software in 1953 — to the ridicule of his colleagues — and how the idea of a computer whose code was separate from its machinery took hold and changed the way we think about computing forever.

When I first said `software’ out loud, people around me said, “Huh?” From the very beginning I found the word too informal to write and often embarrassing to say. Nevertheless, with smirking trepidation I did occasionally feature the word `software’ in speeches and lectures and media interviews throughout the fifties.

It was just a throw-away thing. The word `software’ was hardly my most notable invention, even back then. Nothing to write home about (I was only 19 years old and still living at home). The word `software’ did not belong in a technical paper (besides, an undergraduate is but a ghostwriter for principal researchers). Then too, I had a reputation at UCLA as a practical joker. Colleagues and friends simply shrugged, no doubt regarding each utterance as a tiresome prank or worse, another offbeat neologism, for which I was also becoming noted.

Nobody in 1953 would have guessed that the silly word would take hold, that within a few decades `software’ would enter the general vocabulary for products and for professions — that a worldwide industry would wear it as a solemn name. You can be sure that if my ego and I had harbored any such glorious visions, then…then, what?

 
(reblogged from Boing Boing)

Tagged , , ,

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)

Tagged , ,