-
Notifications
You must be signed in to change notification settings - Fork 41
/
Copy pathsnoob.c.txt
167 lines (143 loc) · 5.36 KB
/
snoob.c.txt
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
/* Computes the next number with the same number of one-bits. Or, the
next subset of the same size as the given one. */
#include <stdio.h>
#include <stdlib.h>
int ntz(unsigned x) { // Number of trailing zeros.
int n;
if (x == 0) return(32);
n = 1;
if ((x & 0x0000FFFF) == 0) {n = n +16; x = x >>16;}
if ((x & 0x000000FF) == 0) {n = n + 8; x = x >> 8;}
if ((x & 0x0000000F) == 0) {n = n + 4; x = x >> 4;}
if ((x & 0x00000003) == 0) {n = n + 2; x = x >> 2;}
return n - (x & 1);
}
int nlz(unsigned x) {
int n;
if (x == 0) return(32);
n = 0;
if (x <= 0x0000FFFF) {n = n +16; x = x <<16;}
if (x <= 0x00FFFFFF) {n = n + 8; x = x << 8;}
if (x <= 0x0FFFFFFF) {n = n + 4; x = x << 4;}
if (x <= 0x3FFFFFFF) {n = n + 2; x = x << 2;}
if (x <= 0x7FFFFFFF) {n = n + 1;}
return n;
}
int pop(unsigned x) {
x = x - ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x + (x >> 4)) & 0x0F0F0F0F;
x = x + (x << 8);
x = x + (x << 16);
return x >> 24;
}
/* This version is from Hakmem (item 175) converted to C. Caution: Do
not call this with x = 0; it then does a divide by 0. If called with
the largest number with a certain number of 1's (i.e., 11...100...0),
it returns a number smaller than the argument.
It is basically seven ops, one of which is division. */
// ------------------------------ cut ----------------------------------
unsigned snoob(unsigned x) {
unsigned smallest, ripple, ones;
// x = xxx0 1111 0000
smallest = x & -x; // 0000 0001 0000
ripple = x + smallest; // xxx1 0000 0000
ones = x ^ ripple; // 0001 1111 0000
ones = (ones >> 2)/smallest; // 0000 0000 0111
return ripple | ones; // xxx1 0000 0111
}
// ---------------------------- end cut --------------------------------
/* Variation 1: ntz to avoid division. Eight ops. */
unsigned snoob1(unsigned x) {
unsigned smallest, ripple, ones;
// x = xxx0 1111 0000
smallest = x & -x; // 0000 0001 0000
ripple = x + smallest; // xxx1 0000 0000
ones = x ^ ripple; // 0001 1111 0000
ones = ones >> (2 + ntz(x)); // 0000 0000 0111
return ripple | ones; // xxx1 0000 0111
}
/* Variation 2: nlz to avoid division. Nine ops. */
unsigned snoob2(unsigned x) {
unsigned smallest, ripple, ones;
// x = xxx0 1111 0000
smallest = x & -x; // 0000 0001 0000
ripple = x + smallest; // xxx1 0000 0000
ones = x ^ ripple; // 0001 1111 0000
ones = ones>>(33-nlz(smallest)); // 0000 0000 0111
return ripple | ones; // xxx1 0000 0111
}
/* Variation 3: pop to avoid division. Nine ops. */
unsigned snoob3(unsigned x) {
unsigned smallest, ripple, ones;
// x = xxx0 1111 0000
smallest = x & -x; // 0000 0001 0000
ripple = x + smallest; // xxx1 0000 0000
ones = x ^ ripple; // 0001 1111 0000
ones = (1 << // 0000 0000 0111
(pop(ones) - 2)) - 1;
return ripple | ones; // xxx1 0000 0111
}
/* The version below is from Harbison & Steele Fourth Ed. section 7.6.7
(p. 215). Nine ops, not counting the "if" statement. */
unsigned next_set_of_n_elements(unsigned x) {
unsigned smallest, ripple, new_smallest, ones;
if (x == 0) return 0;
smallest = (x & -x);
ripple = x + smallest;
new_smallest = (ripple & -ripple);
ones = ((new_smallest/smallest) >> 1) - 1;
return ripple | ones;
}
/* I ran into this next version in October 2007 on the TopCoder web site:
http://forums.topcoder.com/?module=Message&messageID=574258
The author is David de Kloet. The variable x must be signed,
or after generating a correct sequence, it will generate some incorrect
values and then loop forever. Must have x != 0. After generating the
sequence, it generates 0xFFFFFFFF and sticks at that value.
The number of shifts done in the while-loop is equal to the number of
trailing zeros in the input x. So what is the average? I don't know,
will work on it. The values of x are NOT random, they tend to have more
trailing 0's than purely random numbers would have. (For uniformly
distributed random numbers, the average is 1.)
For a word size of 32, if n (the number of 1-bits) = 1, the average
number of trailing 0's is 15.5 (average of the numbers from 0 t 31). For
n = 2, the average is 10 (I think). It gets lower for higher values of
n. */
int snoob4 (int x) {
int y = x + (x & -x);
x = x & ~y;
while ((x & 1) == 0) x = x >> 1;
x = x >> 1;
return y | x;
}
int main(int argc, char *argv[]) {
int n;
unsigned x, y, z, u, v, w;
if (argc != 2) {
printf("Need exactly one argument, an integer from 1 to 7.\n");
exit(1);
}
n = strtol(argv[1], NULL, 10);
if (n < 1 || n > 7) {
printf("Argument must be an integer from 1 to 7.\n");
exit(1);
}
printf("n = %d\n", n);
x = (1 << n) - 1;
y = x;
z = x;
u = x;
v = x;
w = x;
do {
printf("x, y, z, u, v, w = %02X %02X %02X %02X %02X %02X\n", x, y, z, u, v, w);
y = snoob1(x);
z = snoob2(x);
u = snoob3(x);
v = next_set_of_n_elements(x);
w = snoob4(x);
x = snoob(x);
} while (x <= 255);
return 0;
}