Programmer's Puzzles

Doing Code Katas reminded me of some programmer's puzzles (or exercises if you will) I once stumbled upon. I can't remember where I first saw them, and Google isn't much help. So, I decided to dig them out from ${HOME} and post them here for other peoples enjoyment.

1. Given a pointer to the first node in a singly-linked list, determine in linear time whether the list terminates or has a cycle, without storing to memory.
2. How can you construct a linked list that can be traversed forward and backward using only enough space for one pointer per node, but still allowing the nodes to have arbitrary addresses?
3. Prove or disprove: Any Boolean expression with multiple occurences of at least one variable can be simplified.
4. Can you always divide an integer by a power of two using the sign-extending "arithmetic right shift" instruction? Construct a sequence that works for all inputs on your machine. Would this have been easier to write back in the 60's?
5. If your processor doesn't have a bit population count instruction that counts the 1 bits in a word, construct a fast sequence that does so without looping or loading from memory.
6. Write code that counts the number of rightmost zero bits in a word, again without looping or loading or using a special bit scan instruction. Is it easier to count the number of leftmost zero bits?