Old school coding tricks

In a recent post I talked about some gotcha-type questions / Java quirks, but there’s a more fundamental gap that I see all the time – primarily in coders who have never been forced to program in C/C++ at some point. There are some basic pieces of knowledge, some tricks of the trade that everyone should Just Know™. So, instead of bellyaching about how the world’s going to hell and kids these days and what’re you going to do?, I provide the following list of what I consider “essential knowledge that you probably never learned, didn’t care about, or just forgot”.

  • Powers of two

Yes, seriously. These are special numbers, and you should know them by heart. Specifically, you should know the powers of 2 up to 216, as well as 231 and 232 (approximately). Yes, you should memorize them. You’d be surprised how often you run into 214-1 or 215-1 – recognizing them can save you hours of debugging. Or, suddenly realizing that the reason your code is broken is that you’re multiplying two ints in the millions range, and of course they’re overflowing.

20     1
21     2
22     4
23     8
24     16
25     32
26     64
27     128
28     256
29     512
210    1024
211    2048
212    4096
213    8192
214    16384
215    32768
216    65536
231    a little over 2 billion
232    a little over 4 billion
  • ASCII

There was a time in the 80s when almost every computer manual had an ASCII chart in its appendix. It was so common that it was actually a little weird (and frustrating) when you flipped to the back of a book and there wasn’t one. Knowing your ASCII basics is useful, and frequently helpful in unexpected ways. You should know the following code points by heart:

8     Backspace (^H)
9     Tab (\t) (^I)
10    Line-feed (\n) (^J)
13    Carriage return (\r) (^M)
32    Space
48    0
49    1
...
57    9
65    A
66    B
...
90    Z
97    a
98    b
...
122   z

If you squint closely, you may notice that ‘a’ == (‘A’ | 32). Alternatively, ‘A’ == (‘a’ & ~32). Of course, the same is true for every other ASCII letter, which makes upper/lower-case conversion very straightforward.

It should also be clear that if you’re trying to convert a digit from its ASCII representation to an int, you just have to subtract ‘0’ (i.e., 48).

int num = ch - '0';

I recommend printing out a chart (I like this one) and putting it on your desk somewhere. It’s useful more often than you’d expect – especially when trying to translate URL-encoded % codes.

  • Bit math

I used to ask interview questions requiring bit operations, but no one could do them and it was just too depressing, so I gave up. It’s one of those things – they should be part of every coder’s arsenal of skills.

Setting a bit

a |= (1 << bit_index);

Unsetting a bit

a &= ~(1 << bit_index);

Testing a bit

boolean is_set = (a & (1 << bit_index)) != 0;

Caveat 1: Don’t forget the parentheses! I guarantee you, the order of operations will always be the opposite of what you want.

Caveat 2: Always make sure you have enough bits. You really don’t want to discover that the reason your code is crashing horribly is that you shifted bits off the left side of an int.

  • How integers are represented

All integer values (bytes, shorts, ints, and longs) are represented using two’s complement notation. I.e., positive numbers are what you’d expect them to be (e.g., 6 = 000001102), but negative numbers are represented by the two’s complement, which can be calculated by first inverting the bits, then adding one (e.g., -6 = ~000001102 + 1 = 111110012 + 1 = 111110102).

Why does this make sense? Consider the following numbers:

4       00000100
3       00000011
2       00000010
1       00000001
0       00000000
-1      11111111
-2      11111110
-3      11111101
-4      11111100

Notice that it’s almost as though there were an invisible ninth bit, a “1”, on the left side of the positive numbers. Subtracting 1 from 1000000002 gets you the next logical number (i.e., 1000000002 – 1 = 111111112). Using two’s complement makes addition and subtraction Just Work™ without a lot of fancy logic (and by ignoring overflows).

  • How floating point numbers are represented

Floats have 1 sign bit, 8 exponent bits, and 23 mantissa bits. The sign bit indicates whether the number is positive (0) or negative (1). The exponent is a byte’s worth (-128..127) of exponent, and the mantissa is the part after the decimal, with an implicit 1 in front of the decimal.

S E E E E E E E E M M M M M M M M M M M M M M M M M M M M M M M

In the old days (still true on some processors?), floating point operations took more time than integer operations, because how the hell do you even… Right? (now there’s an evil interview question) Anyway, that’s why some people resorted to fixed point math, resulting in games with all sorts of weird visual artifacts. Which was ok, because everyone was doing it, and that’s what you expected. Or Rogue.

  • How to calculate the index of a range

Let’s say you wanted to know which week something was in. Days 1-7 correspond to week #1, 8-14 to week #2, and so on. You can’t just divide by 7, or you’d end up with 7-13 being week #1, 14-20 being week #2, etc. Instead, you use the following trick.

int num_week = (day + 6) / 7

This gets it so that 0 => 0, 1 – 7 => 1, 8-14 => 2, 15-21 => 3, etc. Or, for centuries:

int century = (year + 99) / 100;

Or, more generally:

int count = (num + size_of_range - 1) / size_of_range

This may seem like an odd little point, but it’s useful more often than you’d expect, and not just for dates.

Final word

And there you have it. If you find yourself thinking “nah, I don’t care about any of these,” you might want to ask yourself why not? Because memorizing the powers of two is hard? Really? And if you find yourself thinking, “ooh, he forgot ___”, please put it into the comments – I’m always looking to learn a new trick!

7 thoughts on “Old school coding tricks

  1. It occurs to me, now that this is up, that there was really only one “trick” – the rest being – “core knowledge”… The dangers of naming a post before writing it…

  2. Random thoughts!

    converting to upper case isn’t quite as simple as ‘A’ | 32, coz you should really test if its convertible to begin with… much safer to use toupper() (for C++) folks. If you do want to do this kind of shinangigans, char c = c + (‘a’ – ‘A’) would probably be safer and considerably more anal – EBCIDC is making a comback, I tell ya… any day now…

    Is it still a decimal point if you’re talking about binary?

    I’m SOO glad you didn’t say >> 1 was equivalent to dividing by 2.

  3. Hi,

    I must confess I didn’t know How to calculate the index of a range. Nice trick!. Thanks for teaching me.

    I’m missing something in this list, boolean algebra, I mean:
    (true & true) == !(false || false)
    and this kind of boolean transformations. It might be included in Bit math section.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s