要使用按位運算符檢查JAVA中的mersenne數字

Question

我希望能夠幫助您使用按位/移位運算符查找mersenne數字。 對於程序的每一次運行，程序都會檢查由常量定義的給定數字範圍。

示例：範圍3430..3440。

我檢查了互聯網，得到了這個mersenne數字的屬性：一個梅森數字在二進制表示中只有1個。第一個數字是1,3,7,15,31,63,127。

如何使用java和邏輯運算符的bitshift運算符檢查mersenne數字？

請幫幫我。提前致謝！

Answer 1

的梅森數可以很容易地通過回吐此前梅森數及附加/預謀上市/把-IT-只要一個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; 
} 

所以你可以從那裏開始，然後繼續用第一個函數產生下一個更高的Mersenne數，直到它增大到大於上限（或者變成-1，這發生在枚舉出適合的最高梅森數之後一個long，如果你想要走得更高，你可以用BigInteger這個更煩人的語法做同樣的事情）。

Answer 2

BigInteger有一個不錯的功能bitCount它將統計數字中設置的位數。請注意，任何mersenne數字加上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); 
}