>>499
BitSetのソースを見る限りでは、それほど遅い処理には思えませんでした。
BitSetを継承して、期待する処理を行うメソッドを追加するのはどうでしょうか?

>>500
実装依存だと思うので、明示的に同期処理をしたほうが無難だと思います。
# 2の演算がアトミックであれば、問題ない