A Computer Science Challenge For CD?

[Gabriel]

Awhile ago there was a jeopardy game on CD which I enjoyed. I thought, why not do a regular challenge that will test the kind of skills you need for FIRST rather than just trivia? Somebody could pose a different problem every week, maybe something that you've come across in your work or in your classes. Does anybody think this is a good idea?

I'll start with a problem I came across recently while working on optimizing a chess program for my AI class. It took me a good three or four hours to solve.

There is a small function that needs to run every time the program considers a move. Because the program searches to a depth of 12 or more moves ahead, hundreds of thousands of possible moves will need to be considered each time the program takes a turn. As a result, this function needs to be as fast as humanly possible. For this reason, it must be written in assembler and it CANNOT use anything costly such as loops. I'll allow you at most ONE if-statement.

This function must count the trailing zeros in a word (32-bits in real life but this doesn't really matter for the problem). For example if the word is ...01000 than the function should return 3. However in this particular assembler (PPC in real life, but lets use pseudo-code to make this easier), there is no instruction to count trailing zeros. There is an instruction to count leading zeros. (Lets call it GLZ)

Your mission, should you choose to accept it, is to count the trailing zeros in a given input using as few lines of a psuedo-code assembler as possible, no loops, no branches, no jumps, nothing costly. Other than GLZ, everything you'll need can be found in the MIPS instruction set, so nothing really obscure. Comment ever line and use labels so I can read your solution. I've come up with two already, but there are probably more out there.

I hope this is a fun problem.