真难
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| class Solution {
public:
vector<int> findClosedNumbers(int num) {
vector<int> ret(2);
int lastO = 0;
int lastZ = -1;
for (int i = 0; i < 31; ++i)
{
auto ju = num & (1 << i);
if (ju)
++lastO;
else if (lastO != 0)
{
lastZ = i;
break;
}
}
if (lastZ == -1)
ret[0] = -1;
else
{
ret[0] = num;
ret[0] += 1 << lastZ;
for (int i = 0; i < lastZ; ++i)
ret[0] |= 1 << i;
for (int i = lastZ - 1; i >= lastO - 1; --i)
ret[0] -= 1 << i;
}
lastO = -1;
lastZ = 0;
for (int i = 0; i < 31; ++i)
{
auto ju = num & (1 << i);
if (ju == 0)
++lastZ;
else if (lastZ != 0)
{
lastO = i;
break;
}
}
if (lastO == -1)
ret[1] = -1;
else
{
ret[1] = num;
for (int i = 0; i <= lastO; ++i)
if (ret[1] & 1 << i)
ret[1] ^= 1 << i;
for (int i = lastO - 1; i >= lastZ - 1; --i)
ret[1] += 1 << i;
}
return ret;
}
};
|
原则:
对于小的数:
找到最靠近低位的一个1，且这个1的右边还有0。将这个1变为0，这一位记为i，然后将这个1以及其右边的所有1(假设共有k个1)都移到i - k ~ i - 1的位置上(就是把1全都放到这个1右边的最高位)，如果在走完31个位后仍旧未找到这样一个1，那么就是不存在。
对于大的数:
找到最靠近低位的一个0，且这个0的右边还有1。将这个0变为1，这一位记为i，然后将这个1右边的所有1(假设共有k个1)都移到0 ~ k - 1的位置上(就是把1全都放到这个位右边的最低位)，如果在走完31个位后仍旧未找到这样一个0，那么就是不存在。
将循环位运算改为单步位运算
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| class Solution {
public:
vector<int> findClosedNumbers(int num) {
vector<int> ret(2);
int lastO = 0;
int lastZ = -1;
for (int i = 0; i < 31; ++i)
{
auto ju = num & (1 << i);
if (ju)
++lastO;
else if (lastO != 0)
{
lastZ = i;
break;
}
}
if (lastZ == -1)
ret[0] = -1;
else
{
ret[0] = num;
ret[0] += 1 << lastZ;
ret[0] &= ~((1 << lastZ) - 1);
ret[0] += (1 << lastO - 1) - 1;
}
lastO = -1;
lastZ = 0;
for (int i = 0; i < 31; ++i)
{
auto ju = num & (1 << i);
if (ju == 0)
++lastZ;
else if (lastZ != 0)
{
lastO = i;
break;
}
}
if (lastO == -1)
ret[1] = -1;
else
{
ret[1] = num;
ret[1] ^= 1 << lastO;
ret[1] |= (1 << lastO) - 1;
ret[1] -= (1 << lastZ - 1) - 1;
}
return ret;
}
};
|