2 Fixed a couple minor mixups

Also, `% 2` and `& 1` have different semantics. Division and modulus usually rounds toward zero, but it's implementation defined. Good ol' `>>` and `&` always rounds toward negative infinity, which (in my opinion) makes a lot more sense. For instance, on my computer:

Hence, use what makes sense. Don't think you're being a good boy by using `/% 2` when you were originally going to write `& 1`.

Also, `% 2` and `& 1` have different semantics. Division and modulus usually rounds toward zero, but it's implementation defined. Good ol' `>>` and always rounds toward negative infinity, which (in my opinion) makes a lot more sense. For instance, on my computer:

Hence, use what makes sense. Don't think you're being a good boy by using `/ 2` when you were originally going to write `& 1`.

Also, `% 2` and `& 1` have different semantics. Division and modulus usually rounds toward zero, but it's implementation defined. Good ol' `>>` and `&` always rounds toward negative infinity, which (in my opinion) makes a lot more sense. For instance, on my computer:

Hence, use what makes sense. Don't think you're being a good boy by using `% 2` when you were originally going to write `& 1`.

1

insert premature-discussion-is-the-root-of-all-evil lecture

That said, here are some habits I've gotten into to avoid unnecessary efficiency, and in some cases, make my code simpler and more correct as well.

This isn't a discussion of general principles, but of some things to be aware of to avoid introducing unnecessary inefficiencies into code.

## Know your big-O

This should probably be merged into the lengthy discussion above. It's pretty much common sense that a loop inside of a loop, where the inner loop repeats a calculation, is gonna be slower. For example:

``````for (i = 0; i < strlen(str); i++) {
...
}
``````

This will take a horrendous amount of time if the string is really long, because the length is being recalculated on every iteration of the loop. Note that GCC actually optimizes this case because `strlen()` is marked as a pure function.

When sorting a million 32-bit integers, bubble sort would be the wrong way to go. In general, sorting can be done in O(n * log n) time (or better, in the case of radix sort), so unless you know your data is going to be small, look for an algorithm that's at least O(n * log n).

Likewise, when dealing with databases, be aware of indexes. If you `SELECT * FROM people WHERE age = 20`, and you don't have an index on people(age), it'll require an O(n) sequential scan rather than a much faster O(log n) index scan.

## Integer arithmetic hierarchy

When programming in C, bear in mind that some arithmetic operations are more expensive than others. For integers, the hierarchy goes something like this (least expensive first):

• `+ - ~ & | ^`
• `<< >>`
• `*`
• `/`

Granted, the compiler will usually optimize things like `n / 2` to `n >> 1` automatically if you're targeting a mainstream computer, but if you're targeting an embedded device, you might not get that luxury.

Also, `% 2` and `& 1` have different semantics. Division and modulus usually rounds toward zero, but it's implementation defined. Good ol' `>>` and always rounds toward negative infinity, which (in my opinion) makes a lot more sense. For instance, on my computer:

``````printf("%d\n", -1 % 2); // -1 (maybe)
printf("%d\n", -1 & 1); // 1
``````

Hence, use what makes sense. Don't think you're being a good boy by using `/ 2` when you were originally going to write `& 1`.

## Expensive floating point operations

Avoid heavy floating point operations like `pow()` and `log()` in code that doesn't really need them, especially when dealing with integers. Take, for example, reading a number:

``````int parseInt(const char *str)
{
const char *p;
int         digits;
int         number;
int         position;

// Count the number of digits
for (p = str; isdigit(*p); p++)
{}
digits = p - str;

// Sum the digits, multiplying them by their respective power of 10.
number = 0;
position = digits - 1;
for (p = str; isdigit(*p); p++, position--)
number += (*p - '0') * pow(10, position);

return number;
}
``````

Not only is this use of `pow()` (and the `int`<->`double` conversions needed to use it) rather expensive, but it creates an opportunity for precision loss (incidentally, the code above doesn't have precision issues). That's why I wince when I see this type of function used in a non-mathematical context.

Also, notice how the "clever" algorithm below, which multiplies by 10 on each iteration, is actually more concise than the code above:

``````int parseInt(const char *str)
{
const char *p;
int         number;

number = 0;
for (p = str; isdigit(*p); p++) {
number *= 10;
number += *p - '0';
}

return number;
}
``````