检查序列中的数字
我正在写一个程序，我在一个编码竞赛网站上找到了一个程序，我已经想出了解决问题的方法，但是，我被困在其中的数学部分，我完全稀释了问题，展示了我所需要的。
首先，我需要检查一个数字是否是序列的一部分，我的序列是2*a+1，其中a是序列中的前一个元素，或者是2^n-1以获得序列中的第n项。所以是1,3,7,15,31,63...
我真的不想创建整个序列，并检查是否存在一个数字，但我不知道有什么更快的方法来做到这一点。
第二，如果给我一个数字，比方说25，我想找出这个数字在我的顺序中的第二个最高数。因此，对于25人，是31人，47人是63人，8人是13人。
我怎样才能不创造出完整的序列来做这些事情。
我在这里看到过不同序列的类似问题，但我仍然不知道如何解决这个问题。
回答 3
Stack Overflow用户
发布于 2013-03-02 05:45:42
首先，为您的序列中的任何术语找到显式公式。我太懒了，无法写出证据，所以只需在序列中的每个术语中添加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维基百科：
整数的二进制表示使得可以应用非常快速的测试来确定给定的正整数x是否为2的幂： 正x是两个⇔(x & (x−1))的幂等于零。
所以要检查一下，就这么做：
bool in_sequence(int n) {
return ((n + 1) & n) == 0;
}Stack Overflow用户
发布于 2013-03-02 05:25:50
正如@Blender已经指出的那样，您的序列本质上是2^n - 1，如果使用整数格式存储它，您可以使用这个技巧：
boolean inSequence(int value) {
for (int i = 0x7FFF; i != 0; i >>>= 1) {
if (value == i) {
return true;
}
}
return false;
}注意，对于序列中的每个元素，其二进制表示将是大量的0，然后是大量的1。
例如，二进制中的7是0000000000000000000000000000111，二进制中的63是0000000000000000000000000111111。
此解决方案从01111111111111111111111111111111开始，并使用无符号位移位，然后比较它是否等于您的值。
又好又简单。
Stack Overflow用户
发布于 2013-03-02 06:17:36
如何找到下一个更高的号码:
例如，我们得到19 ( 10011 )，应该返回31 (11111)
int findNext(int n){
if(n == 0) return 1;
int ret = 2; // start from 10
while( (n>>1) > 0){ // end with 100000
ret<<1;
}
return ret-1;
}https://stackoverflow.com/questions/15170965
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号