64bit以上のビットボードを扱いたい

Question

C言語の一番大きい整数型ってlong long intだと思うんですが、

できればC言語で64bit以上の(できるだけ大きい)ビットボードを扱いたいんです。
何かいい方法はないでしょうか？

シフト演算ばりばり使いたいんです。

配列にするしかありませんかね。

Answer 1

GCC限定(Clangもできるみたい)でよければ、独自拡張である__int128という128bitの整数型が使えます。
GCC Manual 6.8 128-bit Integers
整数型なので算術演算はできるようですが、そのままではリテラルを書く方法やprintfとかで表示する方法がないため、工夫が必要になるようです。

なお、コンパイラが128bit整数を扱えるからと言って、CPUが128bitをそのまま演算できるとは限らないため、コンパイルによりエミュレートしたコードに書き換えられる可能性が大きいです(というか、たぶんできるCPUはまだ存在しない)。少なくとx86_64では遅いようです。参考: messier42の日記： gcc拡張、128bit integer

これよりもっと大きい整数を扱いたい場合は多倍長整数ライブラリ(GMPなど)を使うしかないと思います。他に、PythonやRubyが多倍長整数を実現しているので、そのソースコードを参考にするのも一つかも知れません。

Answer 2

CPUのレジスタ長に限界があるので，64ビットマシンでは64ビットまでしか扱えませんね．
すべてのプログラムは最終的には機械語に翻訳されて実行されますが，
その機械語レベルでは64ビットまでしか扱えないということです．
（アセンブラではmovq，addq，jmpq，callq，retqなどの命令が4バイトと明示した命令です．）

ただし，ハードウェアでは対応していないとしても，ソフトウェアで対応させることは可能です．
通常演算子を持ちいる所を関数呼び出しにすることで，このような問題に対応したプログラムが有ります．
技術計算用Ｃプログラム ソース（多倍長演算）
他にもライブラリなど存在すると思うので，探してみてください．
多倍長整数でビット演算をする，という物があるのかはわからないので，
無ければ上記コードの桁上げを真似すれば良いと思います．
64ビットごとの移動は配列の移動で，
それ以下のビット数の移動はビットマスクを使って&や<<を駆使して実装することになりそうです．

ただし，ソフトウェアで実現している演算のため，
実行速度はハードウェアでやるものに比べ必然的に遅くなってしまいます．

Answer 3

配列はやだとか言っといて申し訳ないんですが、回答いただいた意見を参考に再検討した結果、
unsigned long long int の１次元配列で実現することにしました。

皆さんありがとうございました。

Answer 4

こんにちは。
C++言語になっちゃいますが、Boostの多倍長整数型を使えばメモリの許す限りいくらでも桁を増やせるそうです。

BoostはC++用の超強力、かつ、マルチプラット・フォームで無償のオープンソースなライブラリです。
商用にも使えるかなり緩やかなライセンスです。

Answer 5

https://ipsj.ixsq.nii.ac.jp/ej/index.php?action=pages_view_main&active_action=repository_action_common_download&item_id=82197&item_no=1&attribute_id=1&file_no=1&page_id=13&block_id=8
gpuのマルチコアを活かした多倍長演算です。
local to gpu, gpu to local がボトルネックになりそうなので、gpu コアと gpu のメモリ上だけで演算するのがもっとも速度出そうな、、、ー詳細に見てないけど、c/c++でがんばるなら選択肢のひとつかも。

Comments

[ipadcaron]

adc, sbb っていう多倍長演算用命令があり、足し算して桁あげを+1とか、引き算して桁下がりを-1するとかが簡単にできるようになってます。intel系cpuなら。
pen4 以降だとこの2命令はとてつもなく遅いらしいですが str 命令と組み合わせればメモリーデータをロードして+1、メモリにレジスタ内容を格納して+1とかが簡単にできるのでコンパイラまかせのコードよりは高速に実行できるのではないかと。

Answer 6

gccであればgnu拡張で__int128が使えるかもしれません。

__int128 - Using the GNU Compiler Collection (GCC)

ビット演算、足し算、引き算なら64bit型2～3回分程度のコストでできるでしょう。

Comments

[sharow]

raccyさんの回答と被りました。私の回答は無視してください(投稿自体の削除はできないようなので･･･)。