ホームページ Java &#&チュートリアル ビット単位の演算を使用して、大きな整数が完全な平方であるかどうかをすばやく判断するにはどうすればよいですか?

ビット単位の演算を使用して、大きな整数が完全な平方であるかどうかをすばやく判断するにはどうすればよいですか?

Jan 01, 2025 am 07:23 AM

How Can I Quickly Determine if a Large Integer is a Perfect Square Using Bitwise Operations?

アルゴリズムは指定したコードよりも約 35% 高速ですが、実際の結果は CPU (x86) やプログラミング言語 (C/C) によって異なる場合があります。この記事の方法は 3 つの部分に分かれています:

  1. 明白な答えをフィルタリング: 負の数値を含め、最後の 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;

    ログイン後にコピー
  2. 事前計算されたテーブルを使用して、剰余が平方数であるかどうかを実際にチェックしました。 。
  3. 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

    ログイン後にコピー
  4. この時点で、数値が平方数であるためには、その係数が 8 の 1 でなければなりません。
  5. ヘンゼルの補題の基本構造は次のとおりです。 (注: 未テストのコードです。うまくいかない場合は、t=2 または 8 を試してください。)

    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;

    ログイン後にコピー
    考え方は、各反復で r に 1 ビットを追加するということです。」 (r が のべき乗の平方根であることに注意してください。) 実際の平方根は 2^32 より小さいため、その時点で、r または t/2-r が x の実際の平方根であるかどうかを実際に確認できます。実際のコードでは、次の変更されたループを使用しました:

    1

    2

    if((x & 7) != 1)

        return false;

    ログイン後にコピー
    ここでの速度ゲインは 3 つの方法で取得できます: 事前に計算された開始値 (ループの約 10 回の反復に相当)、ループを早めに終了する、および一部の t 値をスキップします。最後の部分では、z=r-x*x を観察し、ビットトリックを使用して t を 2 を z で割った最大の累乗に設定します。これにより、r 値に影響を与えない t 値をスキップすることができます。私の場合、事前に計算された開始値は、8192 を法とする「最小の正」平方根を選択しました。

    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 サイトの他の関連記事を参照してください。

このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

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

AI Clothes Remover

AI Clothes Remover

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

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

Video Face Swap

Video Face Swap

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

ホットツール

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

SublimeText3 中国語版

SublimeText3 中国語版

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

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

ドリームウィーバー CS6

ドリームウィーバー CS6

ビジュアル Web 開発ツール

SublimeText3 Mac版

SublimeText3 Mac版

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

会社のセキュリティソフトウェアはアプリケーションの実行に失敗していますか?それをトラブルシューティングと解決する方法は? 会社のセキュリティソフトウェアはアプリケーションの実行に失敗していますか?それをトラブルシューティングと解決する方法は? Apr 19, 2025 pm 04:51 PM

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

名前を数値に変換してソートを実装し、グループの一貫性を維持するにはどうすればよいですか? 名前を数値に変換してソートを実装し、グループの一貫性を維持するにはどうすればよいですか? Apr 19, 2025 pm 11:30 PM

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

MapsTructを使用したシステムドッキングのフィールドマッピングの問題を簡素化する方法は? MapsTructを使用したシステムドッキングのフィールドマッピングの問題を簡素化する方法は? Apr 19, 2025 pm 06:21 PM

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

Intellijのアイデアは、ログを出力せずにSpring Bootプロジェクトのポート番号をどのように識別しますか? Intellijのアイデアは、ログを出力せずにSpring Bootプロジェクトのポート番号をどのように識別しますか? Apr 19, 2025 pm 11:45 PM

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

エンティティクラス変数名をエレガントに取得して、データベースクエリ条件を構築する方法は? エンティティクラス変数名をエレガントに取得して、データベースクエリ条件を構築する方法は? Apr 19, 2025 pm 11:42 PM

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

Javaオブジェクトを配列に安全に変換する方法は? Javaオブジェクトを配列に安全に変換する方法は? Apr 19, 2025 pm 11:33 PM

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

Redisキャッシュソリューションを使用して、製品ランキングリストの要件を効率的に実現する方法は? Redisキャッシュソリューションを使用して、製品ランキングリストの要件を効率的に実現する方法は? Apr 19, 2025 pm 11:36 PM

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

eコマースプラットフォームSKUおよびSPUデータベースデザイン:ユーザー定義の属性と原因のない製品の両方を考慮する方法は? eコマースプラットフォームSKUおよびSPUデータベースデザイン:ユーザー定義の属性と原因のない製品の両方を考慮する方法は? Apr 19, 2025 pm 11:27 PM

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

See all articles