Next Number: Given a positive integer, print the next smallest and the previous largest number that have the same number of 1 bits in their binary representation.
Hints: #147, #175, #242, #312, #339, #358, #375, #390
解法
问题是，给一个正整数，求下一个最小的和前一个最大的1的数量一样的数字。所谓的最小的和最大的都比给的数字要大。
Next Smallest：
1
2
3
4
5
6
7
8
9
10
11
12
13
|
假设整数为8bit
v
Input: 0 0 0 0 0 0 0 1
Small: 0 0 0 0 0 0 1 0
v
Input: 0 0 0 0 0 0 1 1
Small: 0 0 0 0 0 1 0 1
v
Input: 0 0 0 0 1 0 1 0
Small: 0 0 0 0 1 1 0 0
v
Input: 0 0 1 0 1 1 1 0
Small: 0 0 1 1 0 0 1 1
|
Next Smallest的规律：
- 找到第一个
0，这个非尾部0，它的位置用p表示
- 把这个
0变成1
1
2
3
4
|
index: 7 6 5 4 3 2 1 0
num: 0 1 0 0 1 1 1 0 p = 4, c0 = 1, c1 = 3
a: 0 0 0 1 0 0 0 0 a = 1 << p
n: 0 1 0 1 1 1 1 0 n = num | a
|
1
2
3
4
5
6
|
index: 7 6 5 4 3 2 1 0
num: 0 1 0 1 1 1 1 0 p = 4
a: 0 0 0 1 0 0 0 0 a = 1 << p
b: 0 0 0 0 1 1 1 1 b = a - 1
mask: 1 1 1 1 0 0 0 0 mask = ~b
n: 0 1 0 1 0 0 0 0 n = num & mask
|
1
2
3
4
5
|
index: 7 6 5 4 3 2 1 0
num: 0 1 0 1 0 0 0 0 c1 = 3
a: 0 0 0 0 0 1 0 0 a = 1 << (c1 - 1)
b: 0 0 0 0 0 0 1 1 b = a - 1
n: 0 1 0 1 0 0 1 1 n = num | b
|
代码：
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
|
public int nextSmall(int num) {
int c0 = 0;
int c1 = 0;
int c = num;
while (c & 1 == 0 && c != 0) {
c0++;
c = c >>> 1;
}
while (c & 1 == 1 && c != 0) {
c1++;
c = c >>> 1;
}
if (c0 + c1 > 31 || c0 + c1 == 0) {
// 是负数了
return -1;
}
int p = c0 + c1;
// p位设1
num |= 1 << p;
// 把p右边的清零
num &= ~((1 << p) - 1);
// 在最右侧设置1
num |= 1 << (c1 - 1) - 1;
return num;
}
|
Previous Biggest，和Next Smallest反过来做：
1
2
|
index: 7 6 5 4 3 2 1 0
num: 0 1 0 1 0 0 1 1 p = 4, c1 = 2, c0 = 2
|
1
2
3
4
5
|
index: 7 6 5 4 3 2 1 0
num: 0 1 0 1 0 0 1 1 p = 4
a: 0 0 0 1 0 0 0 0 a = 1 << p
b: 1 1 1 0 1 1 1 1 b = ~a
n: 0 1 0 0 0 0 1 1 n = num & b
|
1
2
3
4
5
|
index: 7 6 5 4 3 2 1 0
num: 0 1 0 0 0 0 1 1 p = 4
a: 0 0 0 1 0 0 0 0 a = 1 << p
b: 0 0 0 0 1 1 1 1 b = a - 1
n: 0 1 0 0 1 1 1 1 n = num | b
|
1
2
3
4
5
6
|
index: 7 6 5 4 3 2 1 0
num: 0 1 0 0 1 1 1 1 p = 4, c0 = 2
a: 0 0 0 0 0 0 1 0 a = 1 << (c0 - 1)
b: 0 0 0 0 0 0 0 1 b = a - 1
c: 1 1 1 1 1 1 1 0 c = ~b
n: 0 1 0 0 1 1 1 0 n = n & c
|
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
public int prevBiggest(int num) {
int c = num;
int c0 = 0;
int c1 = 0;
while (c & 1 == 1 && c != 0) {
c1++;
c >>>= 1;
}
while (c & 0 == 0 && c != 0) {
c0++;
c >>>= 1;
}
if (c0 + c1 > 31 || c0 + c1 == -1) {
return -1;
}
int p = c0 + c1;
// p位设0
num &= ~(1 << p);
// p右边都设1
num |= (1 << p) - 1;
// 从最右设c0 - 1个0
num &= ~(1 << (c0 - 1) - 1)
}
|
评论