-
Notifications
You must be signed in to change notification settings - Fork 0
/
2_66.c
85 lines (83 loc) · 2.61 KB
/
2_66.c
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <stdio.h>
/*
* Generate mask indicating leftmost 1 in x. Assume w = 32. For example 0xFF00 -> 0x8000, and 0x6600 --> 0x4000.
* If x = 0, then return 0;
* 00000000 00000000 11111111 00000000
* =>
* 00000000 00000000 10000000 00000000
*
* 00000000 00000000 01100110 00000000
* =>
* 00000000 00000000 01000000 00000000
*
* 把最左边的1及其往后的位全都变成1，然后再右移1位再相减就得到所需掩码。
* x = x | x >> 1 最左1的个数翻倍
* x = x | x >> 2 最左1的个数再翻倍
* x = x | x >> 4 最左1的个数再翻倍
* x = x | x >> 8 最左1的个数再翻倍
* x = x | x >> 16 最左1的个数再翻倍
* 最极端的情况最左1在最高位，最后一步保证32个位全是1，右移1位再相减就得到掩码。。
*
* 10000000000000000000000000000000
* | 10000000000000000000000000000000
* ----------------------------------
* 11000000000000000000000000000000
*
* 11000000000000000000000000000000
* | 11000000000000000000000000000000
* ----------------------------------
* 11110000000000000000000000000000
*
* 11110000000000000000000000000000
* | 11110000000000000000000000000000
* ----------------------------------
* 11111111000000000000000000000000
*
* 11111111000000000000000000000000
* | 11111111000000000000000000000000
* ----------------------------------
* 11111111111111110000000000000000
*
* 11111111111111110000000000000000
* | 11111111111111110000000000000000
* ----------------------------------
* 11111111111111111111111111111111
*
* 11111111111111111111111111111111
* - 11111111111111111111111111111111
* ----------------------------------
* 10000000000000000000000000000000
*/
int leftmost_one(unsigned x) {
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
return x - (x >> 1);
}
/*
* uname -a
* Darwin MacBook-Pro 15.0.0 Darwin Kernel Version 15.0.0: Sat Sep 19 15:53:46 PDT 2015; root:xnu-3247.10.11~1/RELEASE_X86_64 x86_64
* gcc -o main 2_66.c
* ./main
* x = 0x0000ff00, mask = 0x00008000
* x = 0x00004000, mask = 0x00004000
* x = 0x80000000, mask = 0x80000000
* x = 0xffffffff, mask = 0x80000000
* x = 0x00000000, mask = 0x00000000
*/
int main(void)
{
unsigned x = 0xFF00;
printf("x = 0x%.8x, mask = 0x%.8x\n", x, leftmost_one(x));
x = 0x4000;
printf("x = 0x%.8x, mask = 0x%.8x\n", x, leftmost_one(x));
x = 0x80000000;
printf("x = 0x%.8x, mask = 0x%.8x\n", x, leftmost_one(x));
x = 0xFFFFFFFF;
printf("x = 0x%.8x, mask = 0x%.8x\n", x, leftmost_one(x));
x = 0;
printf("x = 0x%.8x, mask = 0x%.8x\n", x, leftmost_one(x));
return 0;
}