| 15 | typename T |
| 16 | > |
| 17 | T count_bits ( |
| 18 | T v |
| 19 | ) |
| 20 | /*! |
| 21 | requires |
| 22 | - T is an unsigned integral type |
| 23 | ensures |
| 24 | - returns the number of bits in v which are set to 1. |
| 25 | !*/ |
| 26 | { |
| 27 | COMPILE_TIME_ASSERT(is_unsigned_type<T>::value && sizeof(T) <= 8); |
| 28 | |
| 29 | // This bit of bit trickery is from: |
| 30 | // http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSet64 |
| 31 | |
| 32 | v = v - ((v >> 1) & (T)~(T)0/3); |
| 33 | v = (v & (T)~(T)0/15*3) + ((v >> 2) & (T)~(T)0/15*3); |
| 34 | v = (v + (v >> 4)) & (T)~(T)0/255*15; |
| 35 | return (T)(v * ((T)~(T)0/255)) >> (sizeof(T) - 1) * CHAR_BIT; |
| 36 | } |
| 37 | |
| 38 | // ---------------------------------------------------------------------------------------- |
| 39 |
no outgoing calls