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