77 |
78 |
78 // Count returns the number of CPUs in the set s. |
79 // Count returns the number of CPUs in the set s. |
79 func (s *CPUSet) Count() int { |
80 func (s *CPUSet) Count() int { |
80 c := 0 |
81 c := 0 |
81 for _, b := range s { |
82 for _, b := range s { |
82 c += onesCount64(uint64(b)) |
83 c += bits.OnesCount64(uint64(b)) |
83 } |
84 } |
84 return c |
85 return c |
85 } |
86 } |
86 |
|
87 // onesCount64 is a copy of Go 1.9's math/bits.OnesCount64. |
|
88 // Once this package can require Go 1.9, we can delete this |
|
89 // and update the caller to use bits.OnesCount64. |
|
90 func onesCount64(x uint64) int { |
|
91 const m0 = 0x5555555555555555 // 01010101 ... |
|
92 const m1 = 0x3333333333333333 // 00110011 ... |
|
93 const m2 = 0x0f0f0f0f0f0f0f0f // 00001111 ... |
|
94 const m3 = 0x00ff00ff00ff00ff // etc. |
|
95 const m4 = 0x0000ffff0000ffff |
|
96 |
|
97 // Implementation: Parallel summing of adjacent bits. |
|
98 // See "Hacker's Delight", Chap. 5: Counting Bits. |
|
99 // The following pattern shows the general approach: |
|
100 // |
|
101 // x = x>>1&(m0&m) + x&(m0&m) |
|
102 // x = x>>2&(m1&m) + x&(m1&m) |
|
103 // x = x>>4&(m2&m) + x&(m2&m) |
|
104 // x = x>>8&(m3&m) + x&(m3&m) |
|
105 // x = x>>16&(m4&m) + x&(m4&m) |
|
106 // x = x>>32&(m5&m) + x&(m5&m) |
|
107 // return int(x) |
|
108 // |
|
109 // Masking (& operations) can be left away when there's no |
|
110 // danger that a field's sum will carry over into the next |
|
111 // field: Since the result cannot be > 64, 8 bits is enough |
|
112 // and we can ignore the masks for the shifts by 8 and up. |
|
113 // Per "Hacker's Delight", the first line can be simplified |
|
114 // more, but it saves at best one instruction, so we leave |
|
115 // it alone for clarity. |
|
116 const m = 1<<64 - 1 |
|
117 x = x>>1&(m0&m) + x&(m0&m) |
|
118 x = x>>2&(m1&m) + x&(m1&m) |
|
119 x = (x>>4 + x) & (m2 & m) |
|
120 x += x >> 8 |
|
121 x += x >> 16 |
|
122 x += x >> 32 |
|
123 return int(x) & (1<<7 - 1) |
|
124 } |
|