1// Copyright (c) 2014 The mathutil 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 mathutil
6
7import (
8	"math/big"
9)
10
11// BitLenByte returns the bit width of the non zero part of n.
12func BitLenByte(n byte) int {
13	return log2[n] + 1
14}
15
16// BitLenUint16 returns the bit width of the non zero part of n.
17func BitLenUint16(n uint16) int {
18	if b := n >> 8; b != 0 {
19		return log2[b] + 8 + 1
20	}
21
22	return log2[n] + 1
23}
24
25// BitLenUint32 returns the bit width of the non zero part of n.
26func BitLenUint32(n uint32) int {
27	if b := n >> 24; b != 0 {
28		return log2[b] + 24 + 1
29	}
30
31	if b := n >> 16; b != 0 {
32		return log2[b] + 16 + 1
33	}
34
35	if b := n >> 8; b != 0 {
36		return log2[b] + 8 + 1
37	}
38
39	return log2[n] + 1
40}
41
42// BitLen returns the bit width of the non zero part of n.
43func BitLen(n int) int { // Should handle correctly [future] 64 bit Go ints
44	if IntBits == 64 {
45		return BitLenUint64(uint64(n))
46	}
47
48	if b := byte(n >> 24); b != 0 {
49		return log2[b] + 24 + 1
50	}
51
52	if b := byte(n >> 16); b != 0 {
53		return log2[b] + 16 + 1
54	}
55
56	if b := byte(n >> 8); b != 0 {
57		return log2[b] + 8 + 1
58	}
59
60	return log2[byte(n)] + 1
61}
62
63// BitLenUint returns the bit width of the non zero part of n.
64func BitLenUint(n uint) int { // Should handle correctly [future] 64 bit Go uints
65	if IntBits == 64 {
66		return BitLenUint64(uint64(n))
67	}
68
69	if b := n >> 24; b != 0 {
70		return log2[b] + 24 + 1
71	}
72
73	if b := n >> 16; b != 0 {
74		return log2[b] + 16 + 1
75	}
76
77	if b := n >> 8; b != 0 {
78		return log2[b] + 8 + 1
79	}
80
81	return log2[n] + 1
82}
83
84// BitLenUint64 returns the bit width of the non zero part of n.
85func BitLenUint64(n uint64) int {
86	if b := n >> 56; b != 0 {
87		return log2[b] + 56 + 1
88	}
89
90	if b := n >> 48; b != 0 {
91		return log2[b] + 48 + 1
92	}
93
94	if b := n >> 40; b != 0 {
95		return log2[b] + 40 + 1
96	}
97
98	if b := n >> 32; b != 0 {
99		return log2[b] + 32 + 1
100	}
101
102	if b := n >> 24; b != 0 {
103		return log2[b] + 24 + 1
104	}
105
106	if b := n >> 16; b != 0 {
107		return log2[b] + 16 + 1
108	}
109
110	if b := n >> 8; b != 0 {
111		return log2[b] + 8 + 1
112	}
113
114	return log2[n] + 1
115}
116
117// BitLenUintptr returns the bit width of the non zero part of n.
118func BitLenUintptr(n uintptr) int {
119	if b := n >> 56; b != 0 {
120		return log2[b] + 56 + 1
121	}
122
123	if b := n >> 48; b != 0 {
124		return log2[b] + 48 + 1
125	}
126
127	if b := n >> 40; b != 0 {
128		return log2[b] + 40 + 1
129	}
130
131	if b := n >> 32; b != 0 {
132		return log2[b] + 32 + 1
133	}
134
135	if b := n >> 24; b != 0 {
136		return log2[b] + 24 + 1
137	}
138
139	if b := n >> 16; b != 0 {
140		return log2[b] + 16 + 1
141	}
142
143	if b := n >> 8; b != 0 {
144		return log2[b] + 8 + 1
145	}
146
147	return log2[n] + 1
148}
149
150// PopCountByte returns population count of n (number of bits set in n).
151func PopCountByte(n byte) int {
152	return int(popcnt[n])
153}
154
155// PopCountUint16 returns population count of n (number of bits set in n).
156func PopCountUint16(n uint16) int {
157	return int(popcnt[byte(n>>8)]) + int(popcnt[byte(n)])
158}
159
160// PopCountUint32 returns population count of n (number of bits set in n).
161func PopCountUint32(n uint32) int {
162	return int(popcnt[byte(n>>24)]) + int(popcnt[byte(n>>16)]) +
163		int(popcnt[byte(n>>8)]) + int(popcnt[byte(n)])
164}
165
166// PopCount returns population count of n (number of bits set in n).
167func PopCount(n int) int { // Should handle correctly [future] 64 bit Go ints
168	if IntBits == 64 {
169		return PopCountUint64(uint64(n))
170	}
171
172	return PopCountUint32(uint32(n))
173}
174
175// PopCountUint returns population count of n (number of bits set in n).
176func PopCountUint(n uint) int { // Should handle correctly [future] 64 bit Go uints
177	if IntBits == 64 {
178		return PopCountUint64(uint64(n))
179	}
180
181	return PopCountUint32(uint32(n))
182}
183
184// PopCountUintptr returns population count of n (number of bits set in n).
185func PopCountUintptr(n uintptr) int {
186	if UintPtrBits == 64 {
187		return PopCountUint64(uint64(n))
188	}
189
190	return PopCountUint32(uint32(n))
191}
192
193// PopCountUint64 returns population count of n (number of bits set in n).
194func PopCountUint64(n uint64) int {
195	return int(popcnt[byte(n>>56)]) + int(popcnt[byte(n>>48)]) +
196		int(popcnt[byte(n>>40)]) + int(popcnt[byte(n>>32)]) +
197		int(popcnt[byte(n>>24)]) + int(popcnt[byte(n>>16)]) +
198		int(popcnt[byte(n>>8)]) + int(popcnt[byte(n)])
199}
200
201// PopCountBigInt returns population count of |n| (number of bits set in |n|).
202func PopCountBigInt(n *big.Int) (r int) {
203	for _, v := range n.Bits() {
204		r += PopCountUintptr(uintptr(v))
205	}
206	return
207}
208