java - 检查序列中存在的数字

Question

我正在编写一个在编码竞赛网站上找到的程序，我已经想出了解决问题的方法，但是，我被困在其中的数学部分，我完全淡化了问题并展示了我的想法需要。

首先我需要检查一个数字是否是序列的一部分，我的序列是 2*a+1 其中 a 是序列中的前一个元素或 2^n-1 得到第 n序列中的项。所以它是1,3,7,15,31,63...

我真的不想创建整个序列并检查是否存在数字，但我不确定执行此操作的更快方法是什么。

其次，如果给我一个数字，比如 25，我想找出序列中下一个最高的数字。因此，对于 25 岁，它将是 31，对于 47 岁，它将是 63，对于 8 岁，它将是 13。

如何在不创建整个序列的情况下做这些事情。

我在这里看到了不同顺序的类似问题，但我仍然不确定如何解决这个问题

Answer 1

首先为您的序列中的任何项找到明确的公式。我懒得写证明，所以只需将 1 添加到序列中的每个项即可:

 1 + 1 =  2
 3 + 1 =  4
 7 + 1 =  8
15 + 1 = 16
31 + 1 = 32
63 + 1 = 64
...

你可以清楚地看到 a_n = 2^n - 1。

要检查特定数字是否在您的序列中，假设它是:

x = 2^n - 1
x + 1 = 2^n

来自维基百科:

The binary representation of integers makes it possible to apply a very fast test to determine whether a given positive integer x is a power of two:

positive x is a power of two ⇔ (x & (x − 1)) equals to zero.

所以要检查，只需执行以下操作:

bool in_sequence(int n) {
    return ((n + 1) & n) == 0;
}