1
2
3
4
5
6
7
8
9 package bits
10
11 const uintSize = 32 << (^uint(0) >> 32 & 1)
12
13
14 const UintSize = uintSize
15
16
17
18
19 func LeadingZeros(x uint) int { return UintSize - Len(x) }
20
21
22 func LeadingZeros8(x uint8) int { return 8 - Len8(x) }
23
24
25 func LeadingZeros16(x uint16) int { return 16 - Len16(x) }
26
27
28 func LeadingZeros32(x uint32) int { return 32 - Len32(x) }
29
30
31 func LeadingZeros64(x uint64) int { return 64 - Len64(x) }
32
33
34
35
36 const deBruijn32 = 0x077CB531
37
38 var deBruijn32tab = [32]byte{
39 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
40 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9,
41 }
42
43 const deBruijn64 = 0x03f79d71b4ca8b09
44
45 var deBruijn64tab = [64]byte{
46 0, 1, 56, 2, 57, 49, 28, 3, 61, 58, 42, 50, 38, 29, 17, 4,
47 62, 47, 59, 36, 45, 43, 51, 22, 53, 39, 33, 30, 24, 18, 12, 5,
48 63, 55, 48, 27, 60, 41, 37, 16, 46, 35, 44, 21, 52, 32, 23, 11,
49 54, 26, 40, 15, 34, 20, 31, 10, 25, 14, 19, 9, 13, 8, 7, 6,
50 }
51
52
53 func TrailingZeros(x uint) int {
54 if UintSize == 32 {
55 return TrailingZeros32(uint32(x))
56 }
57 return TrailingZeros64(uint64(x))
58 }
59
60
61 func TrailingZeros8(x uint8) int {
62 return int(ntz8tab[x])
63 }
64
65
66 func TrailingZeros16(x uint16) (n int) {
67 if x == 0 {
68 return 16
69 }
70
71 return int(deBruijn32tab[uint32(x&-x)*deBruijn32>>(32-5)])
72 }
73
74
75 func TrailingZeros32(x uint32) int {
76 if x == 0 {
77 return 32
78 }
79
80 return int(deBruijn32tab[(x&-x)*deBruijn32>>(32-5)])
81 }
82
83
84 func TrailingZeros64(x uint64) int {
85 if x == 0 {
86 return 64
87 }
88
89
90
91
92
93
94
95
96
97
98
99 return int(deBruijn64tab[(x&-x)*deBruijn64>>(64-6)])
100 }
101
102
103
104 const m0 = 0x5555555555555555
105 const m1 = 0x3333333333333333
106 const m2 = 0x0f0f0f0f0f0f0f0f
107 const m3 = 0x00ff00ff00ff00ff
108 const m4 = 0x0000ffff0000ffff
109
110
111 func OnesCount(x uint) int {
112 if UintSize == 32 {
113 return OnesCount32(uint32(x))
114 }
115 return OnesCount64(uint64(x))
116 }
117
118
119 func OnesCount8(x uint8) int {
120 return int(pop8tab[x])
121 }
122
123
124 func OnesCount16(x uint16) int {
125 return int(pop8tab[x>>8] + pop8tab[x&0xff])
126 }
127
128
129 func OnesCount32(x uint32) int {
130 return int(pop8tab[x>>24] + pop8tab[x>>16&0xff] + pop8tab[x>>8&0xff] + pop8tab[x&0xff])
131 }
132
133
134 func OnesCount64(x uint64) int {
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154 const m = 1<<64 - 1
155 x = x>>1&(m0&m) + x&(m0&m)
156 x = x>>2&(m1&m) + x&(m1&m)
157 x = (x>>4 + x) & (m2 & m)
158 x += x >> 8
159 x += x >> 16
160 x += x >> 32
161 return int(x) & (1<<7 - 1)
162 }
163
164
165
166
167
168 func RotateLeft(x uint, k int) uint {
169 if UintSize == 32 {
170 return uint(RotateLeft32(uint32(x), k))
171 }
172 return uint(RotateLeft64(uint64(x), k))
173 }
174
175
176
177 func RotateLeft8(x uint8, k int) uint8 {
178 const n = 8
179 s := uint(k) & (n - 1)
180 return x<<s | x>>(n-s)
181 }
182
183
184
185 func RotateLeft16(x uint16, k int) uint16 {
186 const n = 16
187 s := uint(k) & (n - 1)
188 return x<<s | x>>(n-s)
189 }
190
191
192
193 func RotateLeft32(x uint32, k int) uint32 {
194 const n = 32
195 s := uint(k) & (n - 1)
196 return x<<s | x>>(n-s)
197 }
198
199
200
201 func RotateLeft64(x uint64, k int) uint64 {
202 const n = 64
203 s := uint(k) & (n - 1)
204 return x<<s | x>>(n-s)
205 }
206
207
208
209
210 func Reverse(x uint) uint {
211 if UintSize == 32 {
212 return uint(Reverse32(uint32(x)))
213 }
214 return uint(Reverse64(uint64(x)))
215 }
216
217
218 func Reverse8(x uint8) uint8 {
219 return rev8tab[x]
220 }
221
222
223 func Reverse16(x uint16) uint16 {
224 return uint16(rev8tab[x>>8]) | uint16(rev8tab[x&0xff])<<8
225 }
226
227
228 func Reverse32(x uint32) uint32 {
229 const m = 1<<32 - 1
230 x = x>>1&(m0&m) | x&(m0&m)<<1
231 x = x>>2&(m1&m) | x&(m1&m)<<2
232 x = x>>4&(m2&m) | x&(m2&m)<<4
233 x = x>>8&(m3&m) | x&(m3&m)<<8
234 return x>>16 | x<<16
235 }
236
237
238 func Reverse64(x uint64) uint64 {
239 const m = 1<<64 - 1
240 x = x>>1&(m0&m) | x&(m0&m)<<1
241 x = x>>2&(m1&m) | x&(m1&m)<<2
242 x = x>>4&(m2&m) | x&(m2&m)<<4
243 x = x>>8&(m3&m) | x&(m3&m)<<8
244 x = x>>16&(m4&m) | x&(m4&m)<<16
245 return x>>32 | x<<32
246 }
247
248
249
250
251 func ReverseBytes(x uint) uint {
252 if UintSize == 32 {
253 return uint(ReverseBytes32(uint32(x)))
254 }
255 return uint(ReverseBytes64(uint64(x)))
256 }
257
258
259 func ReverseBytes16(x uint16) uint16 {
260 return x>>8 | x<<8
261 }
262
263
264 func ReverseBytes32(x uint32) uint32 {
265 const m = 1<<32 - 1
266 x = x>>8&(m3&m) | x&(m3&m)<<8
267 return x>>16 | x<<16
268 }
269
270
271 func ReverseBytes64(x uint64) uint64 {
272 const m = 1<<64 - 1
273 x = x>>8&(m3&m) | x&(m3&m)<<8
274 x = x>>16&(m4&m) | x&(m4&m)<<16
275 return x>>32 | x<<32
276 }
277
278
279
280
281 func Len(x uint) int {
282 if UintSize == 32 {
283 return Len32(uint32(x))
284 }
285 return Len64(uint64(x))
286 }
287
288
289 func Len8(x uint8) int {
290 return int(len8tab[x])
291 }
292
293
294 func Len16(x uint16) (n int) {
295 if x >= 1<<8 {
296 x >>= 8
297 n = 8
298 }
299 return n + int(len8tab[x])
300 }
301
302
303 func Len32(x uint32) (n int) {
304 if x >= 1<<16 {
305 x >>= 16
306 n = 16
307 }
308 if x >= 1<<8 {
309 x >>= 8
310 n += 8
311 }
312 return n + int(len8tab[x])
313 }
314
315
316 func Len64(x uint64) (n int) {
317 if x >= 1<<32 {
318 x >>= 32
319 n = 32
320 }
321 if x >= 1<<16 {
322 x >>= 16
323 n += 16
324 }
325 if x >= 1<<8 {
326 x >>= 8
327 n += 8
328 }
329 return n + int(len8tab[x])
330 }
331
View as plain text