.config/coc/extensions/coc-go-data/tools/pkg/mod/golang.org/x/tools@v0.0.0-20201028153306-37f0764111ff/container/intsets/util.go

   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
   5 package intsets
   6
   7 // From Hacker's Delight, fig 5.2.
   8 func 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
  17 var a [1 << 8]byte
  18
  19 func 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
  31 func 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.
  44 func 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.
  56 func 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 }