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