Here's an updated patch, that errs on the conservative side:

- rotate instead of shifting, as suggested by Raymond.  This costs
  very little, and I admit to feeling uncomfortable about the
  possibility of just throwing bits away 

- explicit check for -1

- special case for sizeof(void *) = 2*sizeof(long)

All tests pass with the patch applied.  I've left the 'convert to
PyLong' code in as a safety net: it's used on platforms where
sizeof(void *) > sizeof(long) but sizeof(void *) != 2*sizeof(long).  I
don't know of any such platforms in current use.

Sample timings on 64-bit linux (non-debug trunk build, Core 2 Duo).  

before:

dict creation (selected):  1.18751096725
dict creation (shuffled):  1.21234202385
dict creation:  1.00831198692
set creation (selected):  0.869561910629
set creation (shuffled):  0.867420911789
set creation:  0.77153301239

and after:

dict creation (selected):  1.06817317009
dict creation (shuffled):  0.987659931183
dict creation:  0.662216901779
set creation (selected):  0.735805034637
set creation (shuffled):  0.659453868866
set creation:  0.445232152939