-2

整数に0 (ゼロ)があるかどうかを確認する最良の方法は何ですか?

例えば：

505 -> True
555 -> False
44444032 -> True
0000 -> True

私はこれを試しました

public bool has0(int no)
{
    if(no==0)return true;
    while(no!=0)
    {
        if(no%10==0)return true;
        no=no/10;
    }
    return false;
}

これは機能しますが、特に大きな数でこのメソッドを10億回呼び出す必要があるという事実を考えると、大きな数では特に時間がかかります

for(int i=0;i<1000000000;i++)has0(i);

|したがって、 、&、^またはその他の方法などのビットレベル演算子を使用して、数値に 0 が存在するかどうかを確認する最良の方法は何でしょうか。

ありがとう..

4

4 に答える 4

9

モジュロは負荷の高い整数演算です (整数の除算に似ています)。数が偶数かどうかを確認することで、テストで可能な答えの半分を除外できます。モジュロ 10 がゼロに等しい奇数はありません。

if (((no & 0x1) == 0x00) && ((no % 10) == 0)) は true を返します。

偶数の場合は少し高くなりますが、奇数の場合はかなり安くなります。したがって、すべてが偶数である場合、これは役に立ちません (実際には害になります) が、50/50 または 20/80 (20% 奇数) の場合でも、おそらく有利です。

また、整数の乗算はコストが低いため、最初に除算を行って 10 を法として計算することもできます。

while (no)
{
  if (no & 0x1))  // odd?
    no /= 10;
  else  // even
  {
    int nNext = no / 10;  // just do integer divide, and calculate modulo in next line
    if ((no - (10 * nNext)) == 0)  // replaces "more expensive" modulo operation with integer multiply and subtraction
      return true;
    no = nNext;
  }
}
于 2013-07-01T03:45:18.693 に答える
4

受け入れられた答えは元のコードよりも確実に高速ですが、ルックアップ テーブルを使用するアプローチはさらに高速になります。

私の遅いラップトップでは、元のコードで2億5000万の数字を処理するのに約28秒、受け入れられた回答のコードで約23秒かかりました。ルックアップ テーブルを使用すると、 7 秒強かかりました。

コードを見ると、その理由が明らかになります。

bool HasZero(int num)
{
    if (num < 100000) return lookup[num];

    int upperDigits = num / 100000;
    int lowerDigits = num - (upperDigits * 100000);

    return lookup[upperDigits] || lowerDigits < 10000 || lookup[lowerDigits];
}

コードには、最大で 1 つの除算、1 つの減算、1 つの乗算、2 つの比較、および 2 つの配列参照があります。最適化されていても、桁ごとに進むと、それよりもはるかに悪い場合があります。また、ルックアップ テーブルの事前計算にはわずかな時間 (1 ミリ秒未満) がかかります。

32 ビット整数を扱っていない場合、コードはうまく機能しないことに注意してください。3 番目の数字セットを検証する必要があるためです (または、ルックアップ テーブルのサイズを 10^5 から 10^6 に増やす必要があります)。 ; それでも速いと思います。)

于 2013-07-01T05:07:38.770 に答える
0

ちょっとしたアイデアです。定数による除算は、乗算およびシフト シーケンスに置き換えることができます。使用しているコンパイラまたは仮想マシンに手がかりがある場合は、それ自体がこれを行います。ばかげている場合は、乗算とシフトのシーケンスを手動で挿入することで、大幅な高速化を実現できます。たとえば、Java HotSpot Client VM の場合、以下の手法 (非負の n については正しい) は、除算を行う明白な方法 (コメントアウト) よりも 2 倍以上、5 倍高速であることがわかりました。モジュロを使用した元のループとして。

static boolean has0(int n) {
    do {
        //int divided = n / 10;
        int divided = (int)((n * 0xCCCCCCCDL) >>> 35);
        if (divided * 10 == n) return true;
        n = divided;
    } while (n != 0);
    return false;
}

しかし、頭脳明晰ではない Java HotSpot Server VM の場合、明らかな方法はすでに高速であり、このトリックは役に立たないか、遅くすることさえあります。残念ながら、この種の非常に低レベルの最適化では、さまざまな言語や言語の実装に合わせて再調整する準備をする必要があります。

ただし、このようなものを測定しようとする前に、Java でのマイクロベンチマークの奇妙で素晴らしい複雑さについて読んでください。

于 2013-07-11T15:08:39.550 に答える
-4

no==0 の場合、関数は false を返します。それとは別に、どうすればもっとうまくやれるかわかりません。

于 2013-07-01T03:28:24.127 に答える