Javaのベース2コードクエリの戦略が必要

Question

ベース2に変換されないこの問題の戦略を見つけることができますか？あなたはコードを書く必要はありません、ただ私に一般的な戦略を与えてください。ロック、紙「としても知られている（ 『

ラウンド番号

牛、あなたが知っているように、何の指や親指を持っていないので、はさみを再生することができない、紙、石、はさみ』、」Roを、シャム、Bo 'などの名前のホスト）を使用して、誰が最初に搾乳されるような恣意的な決定を下すことができます。彼らは足を使って投げるのは難しいので、コインを裏返すことさえできません。

こうして彼らは「丸数字」マッチングに頼った。最初の牛は20億以下の整数を選ぶ。 2番目の牛も同じです。数字が両方とも「丸数字」である場合、最初の牛が勝ち、それ以外の場合は2番目の牛が勝つ。

正の整数Nは、Nの表現のバイナリが1を持つよりも多くのゼロを持つ場合、「丸数字」と呼ばれます。たとえば、整数9は、バイナリ形式で記述されている場合、1001です。1001には2つのゼロと2つの1があります。従って、9は丸数字である。整数26は2進数で11010です。それは2つのゼロと3つのものを持っているので、それはラウンドナンバーではありません。

もちろん、それはバイナリに番号を変換するために、牛には時間がかかるので、 勝者が決定するためにしばらく時間がかかります。 Bessieは不正行為をしたいと思っており、与えられた範囲内にいくつの「丸数字」があるか知っていれば、彼女はそれを行うことができると考えています。

入力（1 < =開始<完了< = 2,000,000,000）によって与えられる包含的な範囲に表示される丸数字の数を示すプログラムを書くことによって彼女を助けてください。それぞれ二つのスペースで区切られた整数、スタートとフィニッシュ：

入力（rndnum.in） 1行目。

出力（rndnum.out） 行1： 包含範囲内のラウンド番号のカウントである単一の整数Start..Finish

サンプル入力

サンプル出力

Answer 1

あなたの割り当てを理解しているとは思いません。要件は、雌牛は簡単にこの問題を解決することはできませんが、プログラムは許可されていないと述べています。

あなたのプログラムは、与えられた範囲内で、「ラウンド」の数字を動作するようになって、これはバイナリに変換せずに行うのは難しいです。私はあなたの仕事が実際にあなたに求めていると思います。

あなたははバイナリに変換避けなければならない場合は、別の方法があります。次の値を含む、サイズ16の配列を設定することができます番号包括15を介してゼロに1ビットの数を表す

0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 

を。

次に、指定した数値で除算とモジュロを使用すると、その数（および0ビット）で1ビットの数をすばやく取得できます。擬似コードで

：余談として

def getOneBits (num): 
    lookup[] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4}; 
    oneBits = 0 
    for i = 1 to 8: 
     oneBits = oneBits + lookup[num % 16] 
     num = num/16 
    return oneBits 

xstart = 271828 
xend = 314159 
xcount = 0 
for i = start to end: 
    if getOneBits (i) <= 16: 
     xcount = count + 1 
print "There are " xcount " round numbers between " xstart " and " xend 

、サイズ256（代わりにニブルのバイト）のルックアップテーブルを使用して、Cでこれをコーディング、私は約6までの時間を得ることができわずかな最適化作業で数秒で完了しました。