問題タブ [bitcount]

私はJavaを使用しており、チェスエンジンをコーディングしています。

バイト内の最初の1ビットのインデックスと最後の1ビットのインデックスを見つけようとしています。

私は現在JavaでLong.numberOfTrailingZeros（）（またはそのようなもの）を使用しており、バイトを除いてその機能をエミュレートしたいと思います。

それは次のようなものでしょうか：

もしそうなら、bitCountを比較的効率的に実装するにはどうすればよいでしょうか。私は良い説明を気にしません、ただ私にコードを与えないでください。

2 の累乗であることがわかっている数値の 2 を底とする対数を取得するための最適なソリューションは何ですか ( 2^k)。(もちろん、私はそれ自体では2^kなく値だけを知っていkます。)

私が考えた 1 つの方法は、1 を減算してからビットカウントを行うことです。

しかし、（キャッシュなしで）それを行うより速い方法はありますか？また、ビットカウントがそれほど速くないことを知っておくといいですか?

これは次のアプリケーションの 1 つです。

キャッシュなしでbitcountよりも高速であるためO(lg(k))にkは、ストレージ ビットのカウントよりも高速である必要があります。

入力のセットビット数を数えることについて多くの質問を見てきましたinsert type ofが、なぜそれが役立つのですか？

ビットカウントに関するアルゴリズムをお探しの方は、こちらをご覧ください。

1. unsignedlongsのシーケンスで共通ビットをカウントする
2. unsignedintのビット遷移の数をカウントする最速の方法
3. 32ビット整数のセットビット数を数える方法は？

整数のビット長、つまり Python で正の整数を表すのに必要なビット数を取得するにはどうすればよいですか?

http://www-graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

これは Python でも同じ問題です: Python は Bit Twiddling Hacks の C コードに相当しますか?

整数サイズとは別に、PHP でこのコードを使用する必要があります (上記のコードは 128 ビット整数まで機能しますが、これで問題ありません)。これが私が試したことです：

これが機能しない理由 (64 ビット PHP を搭載した 64 ビット マシン - Debian Squeeze) は、PHP が 64 ビットの符号なし整数をサポートしていないように見えるためです ( PHP で 64 ビット整数を使用するには? )。残念ながら、任意精度の数学ライブラリを使用する必要があります。それとも別の方法がありますか？

2 つのバイナリ値があるとします。

MySQL で異なるビット数を取得するにはどうすればよいですか? 私は試した

これは 6 を返しますが、この例では 1 を返すソリューションが必要です。

MySQLのbit_count関数は、場合によっては非常に便利です。

http://dev.mysql.com/doc/refman/5.5/en/bit-functions.html#function_bit-count

それをサポートしていない他のデータベースでその関数を使用したいと思います。これを行う最も簡単な方法は何ですか（DDLレベルでクライアントデータベースにアクセスできないため、ストアド関数を作成せずに）。

かなり冗長なオプションの1つは、これです（TINYINTデータ型の場合）。

Sybase SQL Anywhereの場合、>>演算子は使用できないように見えるため、除算2, 4, 8, 16も機能します。

他の、より冗長でないオプションはありますか？

ビットカウントはいくつかの方法で行うことができます。セットビット反復子、アンセットビット反復子、ルックアップテーブルまたは並列カウントを使用した事前計算済みビット。私がウェブを検索して理解したように、未設定のビットが少ない場合は未設定のビット反復子が高速であり、反対の場合はビット反復子が設定されます。しかし、並列カウント、特に MIT HAKMEM (以下を参照) を使用する必要があるのはいつですか? おそらくルックアップテーブルよりも遅いですが、かなり速いようです。速度の点で、ビットを設定/設定解除するよりも常に優れていますか? 速度とメモリ以外にどちらを選択するかについて、他に考慮すべき点はありますか?

int は 2 の補数で 32 ビットであると想定できます。正当な演算子は次のとおりです。〜＆^ | + << >>

この時点で、私はブルートフォースを使用しています

... 最後の 2 つのステートメントが 32 回繰り返されます。これにより、x が 1 桁シフトされるたびに a に 1 が追加され、32 ビットすべてに対して != 0 になります。

テスト コンパイラを使用すると、テスト ケース 0x7FFFFFFF (0 の後に 31 個の 1 が続く) でメソッドが失敗し、この数値を表すには 32 ビットが必要であると表示されます。これが 31 ではない理由がわかりません (私の方法で計算します) 誰か理由を説明できますか? そして、これを説明するために何を変更する必要がありますか?

非常に大きなビットベクトル（つまり、100,000ビット）に設定されているビットをカウントしたいと思います。

私が現在行っているのは、charへのポインター（つまり、char * cPtr）を使用して、ビット配列の先頭を指すことです。そして私は・・・それから私は：

代わりにshortintポインター（つまり、short int * sPtr）を使用すると、ルックアップの数は半分になりますが、65534要素のルックアップテーブルを使用すると、独自のコストが発生します。メモリ使用量。

毎回調べるのに最適なビット数はいくつなのか気になります。また、その数値がプリセットタイプのサイズではない場合、ビットベクトルをたどって、ビット配列の開始位置を超えた任意のビット数にポインタを設定するにはどうすればよいですか。

ビットをカウントする方法は他にもあることは知っていますが、今のところ、他の方法と比較する前に、この方法を最適化できることを確認したいと思います。