1 // Copyright 2017 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
5 //go:generate go run make_tables.go
7 // Package bits implements bit counting and manipulation
8 // functions for the predeclared unsigned integer types.
11 const uintSize
= 32 << (^uint(0) >> 32 & 1) // 32 or 64
13 // UintSize is the size of a uint in bits.
14 const UintSize
= uintSize
16 // --- LeadingZeros ---
18 // LeadingZeros returns the number of leading zero bits in x; the result is UintSize for x == 0.
19 func LeadingZeros(x
uint) int { return UintSize
- Len(x
) }
21 // LeadingZeros8 returns the number of leading zero bits in x; the result is 8 for x == 0.
22 func LeadingZeros8(x
uint8) int { return 8 - Len8(x
) }
24 // LeadingZeros16 returns the number of leading zero bits in x; the result is 16 for x == 0.
25 func LeadingZeros16(x
uint16) int { return 16 - Len16(x
) }
27 // LeadingZeros32 returns the number of leading zero bits in x; the result is 32 for x == 0.
28 func LeadingZeros32(x
uint32) int { return 32 - Len32(x
) }
30 // LeadingZeros64 returns the number of leading zero bits in x; the result is 64 for x == 0.
31 func LeadingZeros64(x
uint64) int { return 64 - Len64(x
) }
33 // --- TrailingZeros ---
35 // See http://supertech.csail.mit.edu/papers/debruijn.pdf
36 const deBruijn32
= 0x077CB531
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,
43 const deBruijn64
= 0x03f79d71b4ca8b09
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,
52 // TrailingZeros returns the number of trailing zero bits in x; the result is UintSize for x == 0.
53 func TrailingZeros(x
uint) int {
55 return TrailingZeros32(uint32(x
))
57 return TrailingZeros64(uint64(x
))
60 // TrailingZeros8 returns the number of trailing zero bits in x; the result is 8 for x == 0.
61 func TrailingZeros8(x
uint8) int {
62 return int(ntz8tab
[x
])
65 // TrailingZeros16 returns the number of trailing zero bits in x; the result is 16 for x == 0.
66 func TrailingZeros16(x
uint16) (n
int) {
70 // see comment in TrailingZeros64
71 return int(deBruijn32tab
[uint32(x
&-x
)*deBruijn32
>>(32-5)])
74 // TrailingZeros32 returns the number of trailing zero bits in x; the result is 32 for x == 0.
75 func TrailingZeros32(x
uint32) int {
79 // see comment in TrailingZeros64
80 return int(deBruijn32tab
[(x
&-x
)*deBruijn32
>>(32-5)])
83 // TrailingZeros64 returns the number of trailing zero bits in x; the result is 64 for x == 0.
84 func TrailingZeros64(x
uint64) int {
88 // If popcount is fast, replace code below with return popcount(^x & (x - 1)).
90 // x & -x leaves only the right-most bit set in the word. Let k be the
91 // index of that bit. Since only a single bit is set, the value is two
92 // to the power of k. Multiplying by a power of two is equivalent to
93 // left shifting, in this case by k bits. The de Bruijn (64 bit) constant
94 // is such that all six bit, consecutive substrings are distinct.
95 // Therefore, if we have a left shifted version of this constant we can
96 // find by how many bits it was shifted by looking at which six bit
97 // substring ended up at the top of the word.
98 // (Knuth, volume 4, section 7.3.1)
99 return int(deBruijn64tab
[(x
&-x
)*deBruijn64
>>(64-6)])
104 const m0
= 0x5555555555555555 // 01010101 ...
105 const m1
= 0x3333333333333333 // 00110011 ...
106 const m2
= 0x0f0f0f0f0f0f0f0f // 00001111 ...
107 const m3
= 0x00ff00ff00ff00ff // etc.
108 const m4
= 0x0000ffff0000ffff
110 // OnesCount returns the number of one bits ("population count") in x.
111 func OnesCount(x
uint) int {
113 return OnesCount32(uint32(x
))
115 return OnesCount64(uint64(x
))
118 // OnesCount8 returns the number of one bits ("population count") in x.
119 func OnesCount8(x
uint8) int {
120 return int(pop8tab
[x
])
123 // OnesCount16 returns the number of one bits ("population count") in x.
124 func OnesCount16(x
uint16) int {
125 return int(pop8tab
[x
>>8] + pop8tab
[x
&0xff])
128 // OnesCount32 returns the number of one bits ("population count") in x.
129 func OnesCount32(x
uint32) int {
130 return int(pop8tab
[x
>>24] + pop8tab
[x
>>16&0xff] + pop8tab
[x
>>8&0xff] + pop8tab
[x
&0xff])
133 // OnesCount64 returns the number of one bits ("population count") in x.
134 func OnesCount64(x
uint64) int {
135 // Implementation: Parallel summing of adjacent bits.
136 // See "Hacker's Delight", Chap. 5: Counting Bits.
137 // The following pattern shows the general approach:
139 // x = x>>1&(m0&m) + x&(m0&m)
140 // x = x>>2&(m1&m) + x&(m1&m)
141 // x = x>>4&(m2&m) + x&(m2&m)
142 // x = x>>8&(m3&m) + x&(m3&m)
143 // x = x>>16&(m4&m) + x&(m4&m)
144 // x = x>>32&(m5&m) + x&(m5&m)
147 // Masking (& operations) can be left away when there's no
148 // danger that a field's sum will carry over into the next
149 // field: Since the result cannot be > 64, 8 bits is enough
150 // and we can ignore the masks for the shifts by 8 and up.
151 // Per "Hacker's Delight", the first line can be simplified
152 // more, but it saves at best one instruction, so we leave
153 // it alone for clarity.
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
)
161 return int(x
) & (1<<7 - 1)
164 // --- RotateLeft ---
166 // RotateLeft returns the value of x rotated left by (k mod UintSize) bits.
167 // To rotate x right by k bits, call RotateLeft(x, -k).
168 func RotateLeft(x
uint, k
int) uint {
170 return uint(RotateLeft32(uint32(x
), k
))
172 return uint(RotateLeft64(uint64(x
), k
))
175 // RotateLeft8 returns the value of x rotated left by (k mod 8) bits.
176 // To rotate x right by k bits, call RotateLeft8(x, -k).
177 func RotateLeft8(x
uint8, k
int) uint8 {
179 s
:= uint(k
) & (n
- 1)
180 return x
<<s | x
>>(n
-s
)
183 // RotateLeft16 returns the value of x rotated left by (k mod 16) bits.
184 // To rotate x right by k bits, call RotateLeft16(x, -k).
185 func RotateLeft16(x
uint16, k
int) uint16 {
187 s
:= uint(k
) & (n
- 1)
188 return x
<<s | x
>>(n
-s
)
191 // RotateLeft32 returns the value of x rotated left by (k mod 32) bits.
192 // To rotate x right by k bits, call RotateLeft32(x, -k).
193 func RotateLeft32(x
uint32, k
int) uint32 {
195 s
:= uint(k
) & (n
- 1)
196 return x
<<s | x
>>(n
-s
)
199 // RotateLeft64 returns the value of x rotated left by (k mod 64) bits.
200 // To rotate x right by k bits, call RotateLeft64(x, -k).
201 func RotateLeft64(x
uint64, k
int) uint64 {
203 s
:= uint(k
) & (n
- 1)
204 return x
<<s | x
>>(n
-s
)
209 // Reverse returns the value of x with its bits in reversed order.
210 func Reverse(x
uint) uint {
212 return uint(Reverse32(uint32(x
)))
214 return uint(Reverse64(uint64(x
)))
217 // Reverse8 returns the value of x with its bits in reversed order.
218 func Reverse8(x
uint8) uint8 {
222 // Reverse16 returns the value of x with its bits in reversed order.
223 func Reverse16(x
uint16) uint16 {
224 return uint16(rev8tab
[x
>>8]) |
uint16(rev8tab
[x
&0xff])<<8
227 // Reverse32 returns the value of x with its bits in reversed order.
228 func Reverse32(x
uint32) uint32 {
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
237 // Reverse64 returns the value of x with its bits in reversed order.
238 func Reverse64(x
uint64) uint64 {
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
248 // --- ReverseBytes ---
250 // ReverseBytes returns the value of x with its bytes in reversed order.
251 func ReverseBytes(x
uint) uint {
253 return uint(ReverseBytes32(uint32(x
)))
255 return uint(ReverseBytes64(uint64(x
)))
258 // ReverseBytes16 returns the value of x with its bytes in reversed order.
259 func ReverseBytes16(x
uint16) uint16 {
263 // ReverseBytes32 returns the value of x with its bytes in reversed order.
264 func ReverseBytes32(x
uint32) uint32 {
266 x
= x
>>8&(m3
&m
) | x
&(m3
&m
)<<8
270 // ReverseBytes64 returns the value of x with its bytes in reversed order.
271 func ReverseBytes64(x
uint64) uint64 {
273 x
= x
>>8&(m3
&m
) | x
&(m3
&m
)<<8
274 x
= x
>>16&(m4
&m
) | x
&(m4
&m
)<<16
280 // Len returns the minimum number of bits required to represent x; the result is 0 for x == 0.
281 func Len(x
uint) int {
283 return Len32(uint32(x
))
285 return Len64(uint64(x
))
288 // Len8 returns the minimum number of bits required to represent x; the result is 0 for x == 0.
289 func Len8(x
uint8) int {
290 return int(len8tab
[x
])
293 // Len16 returns the minimum number of bits required to represent x; the result is 0 for x == 0.
294 func Len16(x
uint16) (n
int) {
299 return n
+ int(len8tab
[x
])
302 // Len32 returns the minimum number of bits required to represent x; the result is 0 for x == 0.
303 func Len32(x
uint32) (n
int) {
312 return n
+ int(len8tab
[x
])
315 // Len64 returns the minimum number of bits required to represent x; the result is 0 for x == 0.
316 func Len64(x
uint64) (n
int) {
329 return n
+ int(len8tab
[x
])