c++ - 具有一个零位的下一个更高的数字

Question

今天遇到了这个问题，弄了一段时间也没解决。我需要一些帮助

我有数字 N。问题是找到下一个更高的数字 ( > N )，二进制中只有一个零位。

例子:数字 1 可以用二进制表示为 1。下一个只有一个零位的更高数字是 2 - 二进制 10

其他几个例子:
N = 2 (10)，下一个带有一个零位的更高数字是 5 (101)
N = 5 (101)，下一个更高的数字是 6 (110)
N = 7 (111)，下一个更高的数字是 11 (1011)

200个号码列表:

1 1
2 10 - 1
3 11
4 100
5 101 - 1
6 110 - 1
7 111
8 1000
9 1001
10 1010
11 1011 - 1
12 1100
13 1101 - 1
14 1110 - 1
15 1111
16 10000
17 10001
18 10010
19 10011
20 10100
21 10101
22 10110
23 10111 - 1
24 11000
25 11001
26 11010
27 11011 - 1
28 11100
29 11101 - 1
30 11110 - 1
31 11111
32 100000
33 100001
34 100010
35 100011
36 100100
37 100101
38 100110
39 100111
40 101000
41 101001
42 101010
43 101011
44 101100
45 101101
46 101110
47 101111 - 1
48 110000
49 110001
50 110010
51 110011
52 110100
53 110101
54 110110
55 110111 - 1
56 111000
57 111001
58 111010
59 111011 - 1
60 111100
61 111101 - 1
62 111110 - 1
63 111111
64 1000000
65 1000001
66 1000010
67 1000011
68 1000100
69 1000101
70 1000110
71 1000111
72 1001000
73 1001001
74 1001010
75 1001011
76 1001100
77 1001101
78 1001110
79 1001111
80 1010000
81 1010001
82 1010010
83 1010011
84 1010100
85 1010101
86 1010110
87 1010111
88 1011000
89 1011001
90 1011010
91 1011011
92 1011100
93 1011101
94 1011110
95 1011111 - 1
96 1100000
97 1100001
98 1100010
99 1100011
100 1100100
101 1100101
102 1100110
103 1100111
104 1101000
105 1101001
106 1101010
107 1101011
108 1101100
109 1101101
110 1101110
111 1101111 - 1
112 1110000
113 1110001
114 1110010
115 1110011
116 1110100
117 1110101
118 1110110
119 1110111 - 1
120 1111000
121 1111001
122 1111010
123 1111011 - 1
124 1111100
125 1111101 - 1
126 1111110 - 1
127 1111111
128 10000000
129 10000001
130 10000010
131 10000011
132 10000100
133 10000101
134 10000110
135 10000111
136 10001000
137 10001001
138 10001010
139 10001011
140 10001100
141 10001101
142 10001110
143 10001111
144 10010000
145 10010001
146 10010010
147 10010011
148 10010100
149 10010101
150 10010110
151 10010111
152 10011000
153 10011001
154 10011010
155 10011011
156 10011100
157 10011101
158 10011110
159 10011111
160 10100000
161 10100001
162 10100010
163 10100011
164 10100100
165 10100101
166 10100110
167 10100111
168 10101000
169 10101001
170 10101010
171 10101011
172 10101100
173 10101101
174 10101110
175 10101111
176 10110000
177 10110001
178 10110010
179 10110011
180 10110100
181 10110101
182 10110110
183 10110111
184 10111000
185 10111001
186 10111010
187 10111011
188 10111100
189 10111101
190 10111110
191 10111111 - 1
192 11000000
193 11000001
194 11000010
195 11000011
196 11000100
197 11000101
198 11000110
199 11000111
200 11001000

Answer 1

一共有三种情况。

1. 数字x 在其二进制表示中有一个以上的零位。这些零位中除了一个之外的所有位都必须用 1“填充”以获得所需的结果。请注意，与仅填充顶部获得的数字相比，通过采用 x 并填充其一个或多个低位零位获得的所有数字在数值上更接近 x -最零位。因此，答案是数字 x，除一个零位外，其他所有位都已填充:只有最高的零位未填充。例如，如果 x=110101001，则答案为 110111111。要得到答案，找到x的最高零位的索引i，然后计算x和的按位或2^i - 1.

本例的 C 代码:

// warning: this assumes x is known to have *some* (>1) zeros!
unsigned next(unsigned x)
{
  unsigned topmostzero = 0;
  unsigned bit = 1;
  while (bit && bit <= x) {
      if (!(x & bit)) topmostzero = bit;
      bit <<= 1;
  }
  return x | (topmostzero - 1);
}

1. 数字 x 在二进制中没有零位。这意味着 x=2^n - 1 对于某些数字 n。根据与上述相同的推理，答案是 2^n + 2^(n-1) - 1。例如，如果 x=111，则答案为 1011。

2. 数字 x 在其二进制表示中恰好有一个零位。我们知道结果必须严格大于x，所以x本身是不允许的答案。如果 x 在其最低有效位中只有零，那么这种情况就简化为情况 #2。否则，零应向右移动一位。假设 x 在其 i 位中为零，则答案在 i-1 位中应为零。例如，如果 x=11011，则结果为 11101。