とりあえずlong*変換とビット演算やったら基準より約3〜6倍速くなりました！
ありがとうございます。

コード：http://ideone.com/En5hTV
Windows7(32bit)+Visual Studio 2008での実行例。
----------------
基準の時間
565635.5μs
1つずつビット演算版の時間
468610.6μs
long変換ビット演算版の時間
112053.6μs
----------------
基準の時間
339519.1μs
1つずつビット演算版の時間
434149.3μs
long変換ビット演算版の時間
88974.3μs
----------------
基準の時間
683335.3μs
1つずつビット演算版の時間
567164.5μs
long変換ビット演算版の時間
123403.8μs
----------------