ビット単位の演算を使用して、大きな整数が完全な平方であるかどうかをすばやく判断するにはどうすればよいですか?
アルゴリズムは指定したコードよりも約 35% 高速ですが、実際の結果は CPU (x86) やプログラミング言語 (C/C) によって異なる場合があります。この記事の方法は 3 つの部分に分かれています:
-
明白な答えをフィルタリング: 負の数値を含め、最後の 4 桁をチェックします (最後の 6 桁をチェックすると判明しました)役に立ちません)、答えは 0 です。 (次のコードを読むとき、私の入力は 2 つの異なる素数の積である int64 であることに注意してください。そのため、255 を法とする平方の余りは約 1/8 しかありません。ただし、私の経験では、モジュロ演算子 (%) を使用するコストが利点を上回るため、255 を使用したちょっとしたトリックを使用して剰余を計算しました。 (良くも悪くも、単語から個々のバイトを読み取るトリックは使用せず、ビット単位の AND とシフトを実行するだけでした。)
1
2
3
4
if
( x < 0 || (x&2) || ((x & 7) == 5) || ((x & 11) == 8) )
return
false;
if
( x == 0 )
return
true;
ログイン後にコピー事前計算されたテーブルを使用して、剰余が平方数であるかどうかを実際にチェックしました。 。 - ヘンゼルの補題に似た方法を使用して平方根を計算しようとしています
1
2
3
4
5
int64 y = x;
y = (y & 4294967295LL) + (y >> 32);
y = (y & 65535) + (y >> 16);
y = (y & 255) + ((y >> 8) & 255) + (y >> 16);
// At this point, y is between 0 and 511. More code can reduce it farther.
ログイン後にコピー: この前は、次の 2 つを使用しました。検索では、すべての剰余を 2 の累乗で除算します:
1
2
3
if
( bad255[y] )
return
false;
// However, I just use a table of size 512
ログイン後にコピー この時点で、数値が平方数であるためには、その係数が 8 の 1 でなければなりません。 -
ヘンゼルの補題の基本構造は次のとおりです。 (注: 未テストのコードです。うまくいかない場合は、t=2 または 8 を試してください。)
考え方は、各反復で r に 1 ビットを追加するということです。」 (r が のべき乗の平方根であることに注意してください。) 実際の平方根は 2^32 より小さいため、その時点で、r または t/2-r が x の実際の平方根であるかどうかを実際に確認できます。実際のコードでは、次の変更されたループを使用しました:1
2
3
4
5
6
7
8
9
10
if
((x & 4294967295LL) == 0)
x >>= 32;
if
((x & 65535) == 0)
x >>= 16;
if
((x & 255) == 0)
x >>= 8;
if
((x & 15) == 0)
x >>= 4;
if
((x & 3) == 0)
x >>= 2;
ログイン後にコピーここでの速度ゲインは 3 つの方法で取得できます: 事前に計算された開始値 (ループの約 10 回の反復に相当)、ループを早めに終了する、および一部の t 値をスキップします。最後の部分では、z=r-x*x を観察し、ビットトリックを使用して t を 2 を z で割った最大の累乗に設定します。これにより、r 値に影響を与えない t 値をスキップすることができます。私の場合、事前に計算された開始値は、8192 を法とする「最小の正」平方根を選択しました。1
2
if
((x & 7) != 1)
return
false;
ログイン後にコピー1
2
3
4
5
int64 t = 4, r = 1;
t <<= 1; r += ((x - r * r) & t) >> 1;
t <<= 1; r += ((x - r * r) & t) >> 1;
t <<= 1; r += ((x - r * r) & t) >> 1;
// Repeat until t is 2^33 or so. Use a loop if you want.
ログイン後にコピーたとえこのコードがすぐに機能しなかったとしても、いくつかのアイデアを楽しんでいただければ幸いです。事前計算されたテーブルを含む完全なテスト コードは次のとおりです。
1
2
3
4
5
6
7
8
9
10
11
12
13
int64 r, t, z;
r = start[(x >> 3) & 1023];
do
{
z = x - r * r;
if
( z == 0 )
return
true;
if
( z < 0 )
return
false;
t = z & (-z);
r += (z & t) >> 1;
if
( r > (t >> 1) )
r = t - r;
}
while
( t <= (1LL << 33) );
ログイン後にコピー
以上がビット単位の演算を使用して、大きな整数が完全な平方であるかどうかをすばやく判断するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

ホットAIツール

Undresser.AI Undress
リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover
写真から衣服を削除するオンライン AI ツール。

Undress AI Tool
脱衣画像を無料で

Clothoff.io
AI衣類リムーバー

Video Face Swap
完全無料の AI 顔交換ツールを使用して、あらゆるビデオの顔を簡単に交換できます。

人気の記事

ホットツール

メモ帳++7.3.1
使いやすく無料のコードエディター

SublimeText3 中国語版
中国語版、とても使いやすい

ゼンドスタジオ 13.0.1
強力な PHP 統合開発環境

ドリームウィーバー CS6
ビジュアル Web 開発ツール

SublimeText3 Mac版
神レベルのコード編集ソフト(SublimeText3)

ホットトピック











一部のアプリケーションが適切に機能しないようにする会社のセキュリティソフトウェアのトラブルシューティングとソリューション。多くの企業は、内部ネットワークセキュリティを確保するためにセキュリティソフトウェアを展開します。 ...

多くのアプリケーションシナリオでソートを実装するために名前を数値に変換するソリューションでは、ユーザーはグループ、特に1つでソートする必要がある場合があります...

システムドッキングでのフィールドマッピング処理は、システムドッキングを実行する際に難しい問題に遭遇することがよくあります。システムのインターフェイスフィールドを効果的にマッピングする方法A ...

intellijideaultimatiateバージョンを使用してスプリングを開始します...

データベース操作にMyBatis-Plusまたはその他のORMフレームワークを使用する場合、エンティティクラスの属性名に基づいてクエリ条件を構築する必要があることがよくあります。あなたが毎回手動で...

Javaオブジェクトと配列の変換:リスクの詳細な議論と鋳造タイプ変換の正しい方法多くのJava初心者は、オブジェクトのアレイへの変換に遭遇します...

Redisキャッシュソリューションは、製品ランキングリストの要件をどのように実現しますか?開発プロセス中に、多くの場合、ランキングの要件に対処する必要があります。

eコマースプラットフォーム上のSKUおよびSPUテーブルの設計の詳細な説明この記事では、eコマースプラットフォームでのSKUとSPUのデータベース設計の問題、特にユーザー定義の販売を扱う方法について説明します。
