下一个更高的数字,一个零位

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.为了得到答案,发现该指数i最上面的零位的x,然后计算该位或中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);
}

2. 数字x在二进制中没有零位.这意味着x=2^n - 1一些数字n.通过与上述相同的推理,答案就是如此2^n + 2^(n-1) - 1.例如,如果x=111,那么答案是1011.

3. 数字x在其二进制表示中恰好具有一个零位.我们知道结果必须严格大于x,所以x不允许自己作为答案.如果x在其最低有效位中只有零,那么这种情况减少到情况#2.否则,零点应该向右移动一个位置.假设x其i第-8位为零,则答案应该在i-1第n位为零.例如,如果x=11011,那么结果是11101.