Clever Programming Tricks

Alan Mycroft

Back to HAKMEMC

All of these tricks are intended to save a factor of at least two (and often ten or more) by local changes to code. Of course algorithmic improvement can provide much greater efficiency gains, so I am assuming that you have done all you can in this respect, BEFORE using these tricks.

Algorithmic Ideas

• Use a lookup table instead of calculating things when needed. Nowadays tables of 10^6 entries are cheap; indeed tables of 10^8 entries can easily be stored on a CD. Example: Noughts and Crosses (Amer. Tic-Tac-Toe): It may be amusing to write a planner for this game, but for efficiency... Pre-compute a table of size at most 3^9 (9 squares holding 0,X or blank) Positions encode `who is to move' by counting 0's and X's. Mark completed games (wins/draws/losses) as 1/0/-1 (unreachable positions like `both sides have won' can be marked randomly, e.g. draw). Back-propagate to mark all positions (using min or max according to turn). This will mark initial position with result if both sides play as well as possible (i.e. draw for this game). Adding a `best move' entry to the table for each position can be done cheaply during back-propagation. Cost is at most 9*3^9 operations (up to 9 predecessors of each position) which is 177147 steps. Cost to play a move is 1 instruction.

Low level hacks

• Determine parity of a 8-bit byte (assumed zero padded). Really this should be done by a lookup-table, but the following idea (adapted from Digital's DEC-10 assembler manual) is pretty:

  int parity(unsigned8 x) {
    return (((x * 0x10101) & 011111111) * 011111111) >> 21 & 1;
    /* MULT makes 3 copies of x, then AND re-selects each bit in `x' only */
    /* once (separated).  MULT adds up all such in bit 21 (cf long        */
    /* multiplication); OK since there can be no carry in to bit 21.      */
  }
  

• Determine if a 32-bit word has a zero (8-bit) byte (useful in strcpy/strcmp)

  int haszerobyte(unsigned32 x) {
    return ((x - 0x01010101) & (~x) & 0x80808080) != 0;
  }
  

• Determine if a 64-bit word has a zero (8-bit) byte (useful in strcpy/strcmp)

  int haszerobyte(unsigned64 x) {
    return ((x - 0x010101010101010) & (~x) & 0x8080808080808080) != 0;
  }
  

• Count the `1' bits in a 9-bit value:

  int count_ones(unsigned36 x) {
    return ((((x * 01001001001) & 0x111111111) % 15;
  }
  

• if A is a 9 bit quantity, B gets number of 1's (Schroeppel)
          IMUL A,[1001001001]     ;4 copies
          AND A,[42104210421]     ;every 4th bit
          IDIVI A,17              ;casting out 15.'s in hexadecimal
  
  ;if A is 6 bit quantity, B gets 6 bits reversed (Schroeppel)
          IMUL A,[2020202]        ;4 copies shifted
          AND A,[104422010]       ;where bits coincide with reverse repeated base 2^8
          IDIVI A,377             ;casting out 2^8 - 1's
  
  ;reverse 7 bits (Schroeppel)
          IMUL A,[10004002001]    ;4 copies sep by 000's base 2 (may set arith. o'flow)
          AND A,[210210210010]    ;where bits coincide with reverse repeated base 2^8
          IDIVI A,377             ;casting out 377's
  
  ;reverse 8 bits (Schroeppel)
          MUL A,[100200401002]    ;5 copies in A and B
          AND B,[20420420020]     ;where bits coincide with reverse repeated base 2^10
          ANDI A,41               ;"
          DIVI A,1777             ;casting out 2^10 - 1's