ビット単位の演算子を使用してJAVAのメルセンヌ数を確認する

Question

ビット単位/ビットシフト演算子を使用してメルセンヌ数を見つけるのに役立つことが必要です。 プログラムの実行ごとに、プログラムは定数で定義されている特定の数値範囲を調べます。

例：範囲は3430.3440です。

私はインターネットをチェックし、このメルセンヌ数の特性を得ました。メルセンヌ数は、バイナリ表現でわずか1で構成されています。最初の数字は1,3,7,15,31,63,127です。

Javaと論理演算子のビットシフト演算子を使用してメルセンヌの数値をチェックするにはどうすればよいですか？

私を助けてください。前もって感謝します！

Answer 1

メルセンヌ数は、前のメルセンヌ数を取ることによって、簡単に一覧表示され、追加/先頭追加/置き、それを-どこ1することができます。

long nextMersenne(long previous) { 
    return (previous << 1) | 1; 
} 

あなたは、小さくない最小のメルセンヌ数を見つけることができます例えば、そのパス内のすべてを設定し、右に左端のセットベットを「掃引」によって与えられた番号を-thanあなたはこのように計算することができ

1001101 
1101101 
1111101 
1111111 

：

long lowestMersenneNotLessThan(long lowerBound) { 
    long x = lowerBound; 
    x |= x >> 1; 
    x |= x >> 2; 
    x |= x >> 4; 
    x |= x >> 8; 
    x |= x >> 16; 
    x |= x >> 32; 
    return x; 
} 

だから、あなたがそこに開始することができ、それが上限よりも大きくなるまで、その後、最初の関数と次に高いメルセンヌ番号を生成しておく（またはに収まる最大のメルセンヌ数を列挙した後に起こった、-1になりますa long、あなたがもっと上に行きたい場合は、BigIntegerというより厄介な構文で同じことをすることができます）。

Answer 2

BigIntegerにはnice機能があります。bitCountは、数字に設定されているビット数をカウントします。メルセンヌの数字に1を加えたものには、ちょうど1ビットが設定されていることに注意してください。

public boolean isMersenne(int n) { 
    // If it is mersenne (i.e. 2^n -1) then n + 1 will have just ONE set bit. 
    return (BigInteger.valueOf(n+1).bitCount() == 1); 

} 

public void test() { 
    int count = 0; 
    for (int i = 1; i < 10000; i++) { 
     if (isMersenne(i)) { 
      System.out.println(i + " is mersenne!"); 
      count += 1; 
     } 
    } 
    System.out.println("There are "+count); 
}