使用按位运算符检查 JAVA 中的梅森数

Question

我需要帮助使用 bitwise/bitshift 运算符查找梅森数。对于程序的每个运行，程序都会检查由常量定义的给定数字范围。

Example : the range 3430..3440.

我上网查了一下，得到了这个属性的梅森数：一个梅森数在二进制表示中只包含 1。第一个数字是 1、3、7、15、31、63、127。

如何使用 java 的位移运算符和逻辑运算符检查梅森数？

请帮帮我。提前致谢！

Answer 1

BigInteger 有一个很好的函数 bitCount 可以计算数字中设置了多少位。请注意，任何梅森数加 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);
}

Answer 2

梅森数可以很容易地列出，取前一个梅森数和appending/prepending/put-it-wherever一个1:

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

您可以找到不小于给定数字的最低梅森数，方法是 "sweeping" 最左边的设置向右下注，设置其路径中的所有内容，例如

你可以这样计算：

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).

使用按位运算符检查 JAVA 中的梅森数

To check mersenne numbers in JAVA using bitwise operator

java

bitwise-operators