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
|
// Copyright 2013 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
package intsets
// From Hacker's Delight, fig 5.2.
func popcountHD(x uint32) int {
x -= (x >> 1) & 0x55555555
x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
x = (x + (x >> 4)) & 0x0f0f0f0f
x = x + (x >> 8)
x = x + (x >> 16)
return int(x & 0x0000003f)
}
var a [1 << 8]byte
func init() {
for i := range a {
var n byte
for x := i; x != 0; x >>= 1 {
if x&1 != 0 {
n++
}
}
a[i] = n
}
}
func popcountTable(x word) int {
return int(a[byte(x>>(0*8))] +
a[byte(x>>(1*8))] +
a[byte(x>>(2*8))] +
a[byte(x>>(3*8))] +
a[byte(x>>(4*8))] +
a[byte(x>>(5*8))] +
a[byte(x>>(6*8))] +
a[byte(x>>(7*8))])
}
// nlz returns the number of leading zeros of x.
// From Hacker's Delight, fig 5.11.
func nlz(x word) int {
x |= (x >> 1)
x |= (x >> 2)
x |= (x >> 4)
x |= (x >> 8)
x |= (x >> 16)
x |= (x >> 32)
return popcount(^x)
}
// ntz returns the number of trailing zeros of x.
// From Hacker's Delight, fig 5.13.
func ntz(x word) int {
if x == 0 {
return bitsPerWord
}
n := 1
if bitsPerWord == 64 {
if (x & 0xffffffff) == 0 {
n = n + 32
x = x >> 32
}
}
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 - int(x&1)
}
|
