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
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.
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!