1// Copyright 2013 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.
4
5package intsets
6
7// From Hacker's Delight, fig 5.2.
8func popcountHD(x uint32) int {
9	x -= (x >> 1) & 0x55555555
10	x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
11	x = (x + (x >> 4)) & 0x0f0f0f0f
12	x = x + (x >> 8)
13	x = x + (x >> 16)
14	return int(x & 0x0000003f)
15}
16
17var a [1 << 8]byte
18
19func init() {
20	for i := range a {
21		var n byte
22		for x := i; x != 0; x >>= 1 {
23			if x&1 != 0 {
24				n++
25			}
26		}
27		a[i] = n
28	}
29}
30
31func popcountTable(x word) int {
32	return int(a[byte(x>>(0*8))] +
33		a[byte(x>>(1*8))] +
34		a[byte(x>>(2*8))] +
35		a[byte(x>>(3*8))] +
36		a[byte(x>>(4*8))] +
37		a[byte(x>>(5*8))] +
38		a[byte(x>>(6*8))] +
39		a[byte(x>>(7*8))])
40}
41
42// nlz returns the number of leading zeros of x.
43// From Hacker's Delight, fig 5.11.
44func nlz(x word) int {
45	x |= (x >> 1)
46	x |= (x >> 2)
47	x |= (x >> 4)
48	x |= (x >> 8)
49	x |= (x >> 16)
50	x |= (x >> 32)
51	return popcount(^x)
52}
53
54// ntz returns the number of trailing zeros of x.
55// From Hacker's Delight, fig 5.13.
56func ntz(x word) int {
57	if x == 0 {
58		return bitsPerWord
59	}
60	n := 1
61	if bitsPerWord == 64 {
62		if (x & 0xffffffff) == 0 {
63			n = n + 32
64			x = x >> 32
65		}
66	}
67	if (x & 0x0000ffff) == 0 {
68		n = n + 16
69		x = x >> 16
70	}
71	if (x & 0x000000ff) == 0 {
72		n = n + 8
73		x = x >> 8
74	}
75	if (x & 0x0000000f) == 0 {
76		n = n + 4
77		x = x >> 4
78	}
79	if (x & 0x00000003) == 0 {
80		n = n + 2
81		x = x >> 2
82	}
83	return n - int(x&1)
84}
85