Handy-Dandy Computer Math Tricks

Credits: I am heavily influenced by the book Algorithms (Sedgewick 1983). IMHO, that book really formed the way I learned to program.

Disclaimer 1: These tricks have probably been discovered elsewhere, I have done no research to find out, they're just things I discovered or hacked together at various times.

Disclaimer 2: I made up all of this stuff over the course of a day, not peeking at anyone else's code. These tricks are just that, tricks. They work as far as I know (and I've done some REASONABLE testing to make sure) but there may be a typo below, or some other machine-specific thing I overlooked, so I make no guarantees.

Mapping a hex digit to its binary equivalent

Example: Accept 'd' or 'D' and return 13

• Trivial:
  The below works just fine. It is O(1) but has a branch, which is usually bad in tight loops, and that is just where we usually find a function like this. Also, toupper() can be complicated.

  	int hexval(char c)
  	{
  		if (c <= '9') return (c - '0');
  		return (toupper(c) - 'A');
  	}
  

• A different take:
  To avoid the branch, we could do a fetch instead. This hits An array can be constructed:

  	int hexval(char c)
  	{
  		static const char lookup[256] =
  		{ -1 ... 0, 1, 2, ... 10, 11, 12... 10, 11, 12... -1 ... }
  
  		return(lookup[c]);
  	}
  

• My favorite:
  This algorithm is of questionable direct value. It's 4 instuctions long, and uses 4 constants, so it may take longer than the first implementations. Nevertheless, the magic nature of the constants here intrigues me.

  	int hexval(char c)
  	{
  		return ((((c & 0x3f) + 9) % 57) & 0x0f);
  	}
  

Converting 4 ascii binary digits to their equivalent value

Example: Accept "0101" and return 5

• Trivial:
  O(n) technically, but O(1) in practice. But k is very high. Still, it works.

  	int binval(char s[4])
  	{
  		int i;
  		int j;
  		for (i = j = 0; i < 4; ++i)
  		{
  			j = (j << 1) | s[i] & 1;
  		}
  		return (j);
  	}
  

• Better:
  O(1), but much lower k. Unroll the loop.

  	int binval(char s[4])
  	{
  		return (
  			(s[3] & 0x01) |
  			((s[2] & 0x01) << 1) |
  			((s[1] & 0x01) << 2) |
  			((s[0] & 0x01) << 3));
  	}
  

• My favorite:
  On a sun, ntohl is free. On an x86, it's one instruction. OK, I admit, it's the magic constants that cause me to like this... But it's O(1) with a k somewhere around 4-5 instructions.

  	int binval(char s[4])
  	{
  		return ((ntohl((*((long *)s)) % 127) % 17);
  	}
  

Is only one bit set?

Example: Accept 1024 or 1048576 and return 1. Accept 0 or 17 and return 0.

• Trivial
  This algorithm does the job, but bites in terms of execution time. It's O(bits-in-an-int) and a medium-sized k. (k would be approximately 9 instructions, including a branch)

  	int onebit (int n)
  	{
  		int i;
  		for (i = 1; i < 8 * sizeof(n); ++i)
  		{
  			if ((n ^ (1 << i)) == 0) return (1);
  		}
  		return (0);
  	}
  

• Better
  This algorithm is less straightforward, but it basically tests to see if any two distinct bits are set at one time. If there are two bits set in a word, they will cause both sides of one of the below "&&" to be true. The masks are drawn from an old bit-counting algorithm, but could be other carefully constructed constants as well. It's O(log-of-bits-in-an-int) and has a medium-sized k. (k would be approximately 7 math-only instructions)

  	int onebit (int n)
  	{
  		return (n &&
  			!((n & 0x0000ffff && n & 0xffff0000) ||
  			  (n & 0x00ff00ff && n & 0xff00ff00) ||
  			  (n & 0x0f0f0f0f && n & 0xf0f0f0f0) ||
  			  (n & 0x33333333 && n & 0xcccccccc) ||
  			  (n & 0x55555555 && n & 0xaaaaaaaa)));
  	}
  

• My favorite
  This algorithm is O(1) and has a k of 3 or 4 instructions

  	int onebit (int n)
  	{
  		return (!(i & (i - 1)));
  	}
  

Back to minutia page