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
13namespace v8 {
14namespace base {
15namespace bits {
16
17template <typename T, bool kMSBFirst = false>
18class BitsIterator : public iterator<std::forward_iterator_tag, int> {
19  STATIC_ASSERT(std::is_integral<T>::value);
20
21 public:
22  explicit BitsIterator(T bits) : bits_(bits) {}
23
24  int operator*() const {
25    return kMSBFirst ? 8 * sizeof(T) - 1 - CountLeadingZeros(bits_)
26                     : CountTrailingZeros(bits_);
27  }
28
29  BitsIterator& operator++() {
30    bits_ &= ~(T{1} << **this);
31    return *this;
32  }
33
34  bool operator==(BitsIterator other) { return bits_ == other.bits_; }
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.
42template <typename T>
43auto 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.
48template <typename T>
49auto 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