java - 计算整数的二进制根(java)

Question

我一直在尝试为与 here 相同的问题找到正确的解决方案但在 Java 中，由于应该返回计数，因此略有修改。

我想出了以下解决方案:

public static int count(int n) {
    // check for 0 or smaller
    if (n <= 0) {
        return -1;
    }

    // find root of N
    int root = (int) Math.ceil(Math.sqrt(n));
    int count = 0;
    for (int i = 1; i < root; i++) {
        if (n % i == 0) {
            // calculate bit_rev(i)
            int reverse = bit_rev(i);

            // calculate bit_rev(N/i)
            int reverseDiv = bit_rev((int)Math.floor(n/i));

            // check whether i * bit_rev(i) == N or i == bit_rev(N/i)
            if (reverse*i == n
                    || i == reverseDiv) {
                System.out.println(String.format("Found reverse (N = %d, i = %d, bit_rev(i) = %d, bit_rev(i) * i = %d, bit_rev(N/i) = %d)", n, i, reverse, reverse*i, reverseDiv));
                count++;
            } else {
                System.out.println(String.format("N = %d mod i = %d == 0, but no match (bit_rev(i) = %d, bit_rev(i) * i = %d, bit_rev(N/i) = %d)", n, i, reverse, reverse*i, reverseDiv));
            }
        }
    }


    if (count == 0) {
        // didn't match -> return -1
        return -1;
    } else {
        // return whatever the count was
        return count;
    }
}

public static int bit_rev(int n) {
    String string = Integer.toBinaryString(n);
    String reverseString = new StringBuffer(string).reverse().toString();
    int reverse = Integer.parseInt(reverseString, 2);
    return reverse;
}

在引用样本中，N = 3245 的解应该是 count = 55。

但是，我的解决方案发现 count = 1 (i = 55, bit_rev(i) = 59)。

其他引用样本是:

-) N = 50 -> count = 1
-) N = 286 -> count = 2

我知道找到 bit_rev() 的解决方案不是最好的(最有效的)，但我不认为这是错误的，不是吗？

这里是不是还有其他错误，还是N = 3245的引用样本有误？

Answer 1

我认为您误读了问题，或者引用答案有误。如果它与 http://algorithmsforever.blogspot.com/2011/12/integer-binary-roots.html?m=1 中的问题类似那么您需要返回最小的二进制根，而不是二进制根的数量。

无论如何，我认为您的实现正确地解决了这些问题。 55 确实是 3245 的最小二进制根(不是根数)。