1 // Copyright 2020 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4 
5 #ifndef V8_BASE_BITS_ITERATOR_H_
6 #define V8_BASE_BITS_ITERATOR_H_
7 
8 #include <type_traits>
9 
10 #include "src/base/bits.h"
11 #include "src/base/iterator.h"
12 
13 namespace v8 {
14 namespace base {
15 namespace bits {
16 
17 template <typename T, bool kMSBFirst = false>
18 class BitsIterator : public iterator<std::forward_iterator_tag, int> {
19   STATIC_ASSERT(std::is_integral<T>::value);
20 
21  public:
BitsIterator(T bits)22   explicit BitsIterator(T bits) : bits_(bits) {}
23 
operator *() const24   int operator*() const {
25     return kMSBFirst ? 8 * sizeof(T) - 1 - CountLeadingZeros(bits_)
26                      : CountTrailingZeros(bits_);
27   }
28 
operator ++()29   BitsIterator& operator++() {
30     bits_ &= ~(T{1} << **this);
31     return *this;
32   }
33 
operator ==(BitsIterator other)34   bool operator==(BitsIterator other) { return bits_ == other.bits_; }
operator !=(BitsIterator other)35   bool operator!=(BitsIterator other) { return bits_ != other.bits_; }
36 
37  private:
38   T bits_;
39 };
40 
41 // Returns an iterable over the bits in {bits}, from LSB to MSB.
42 template <typename T>
IterateBits(T bits)43 auto IterateBits(T bits) {
44   return make_iterator_range(BitsIterator<T>{bits}, BitsIterator<T>{0});
45 }
46 
47 // Returns an iterable over the bits in {bits}, from MSB to LSB.
48 template <typename T>
IterateBitsBackwards(T bits)49 auto IterateBitsBackwards(T bits) {
50   return make_iterator_range(BitsIterator<T, true>{bits},
51                              BitsIterator<T, true>{0});
52 }
53 
54 }  // namespace bits
55 }  // namespace base
56 }  // namespace v8
57 
58 #endif  // V8_BASE_BITS_ITERATOR_H_
59