[base] Add bits::IsPowerOfTwo
Adds helper for computing whether a number is power of two.
Change-Id: Ifd7e01ec1aad644fd9c6ac78600edd013076c9fb
Reviewed-on: https://chromium-review.googlesource.com/1065960
Commit-Queue: Michael Lippautz <mlippautz@chromium.org>
Reviewed-by: Kentaro Hara <haraken@chromium.org>
Reviewed-by: Gabriel Charette <gab@chromium.org>
Cr-Commit-Position: refs/heads/master@{#560988}
CrOS-Libchrome-Original-Commit: b6d0db428b5b19930b17ac94a95eaefed30d26b9
diff --git a/base/bits.h b/base/bits.h
index 7d4d90d..a1c8b5d 100644
--- a/base/bits.h
+++ b/base/bits.h
@@ -21,9 +21,22 @@
namespace base {
namespace bits {
+// Returns true iff |value| is a power of 2.
+template <typename T,
+ typename = typename std::enable_if<std::is_integral<T>::value>>
+constexpr inline bool IsPowerOfTwo(T value) {
+ // From "Hacker's Delight": Section 2.1 Manipulating Rightmost Bits.
+ //
+ // Only positive integers with a single bit set are powers of two. If only one
+ // bit is set in x (e.g. 0b00000100000000) then |x-1| will have that bit set
+ // to zero and all bits to its right set to 1 (e.g. 0b00000011111111). Hence
+ // |x & (x-1)| is 0 iff x is a power of two.
+ return value > 0 && (value & (value - 1)) == 0;
+}
+
// Round up |size| to a multiple of alignment, which must be a power of two.
inline size_t Align(size_t size, size_t alignment) {
- DCHECK_EQ(alignment & (alignment - 1), 0u);
+ DCHECK(IsPowerOfTwo(alignment));
return (size + alignment - 1) & ~(alignment - 1);
}
diff --git a/base/bits_unittest.cc b/base/bits_unittest.cc
index 39bf6b0..98b9c08 100644
--- a/base/bits_unittest.cc
+++ b/base/bits_unittest.cc
@@ -170,5 +170,28 @@
#endif // ARCH_CPU_64_BITS
}
+TEST(BitsTest, PowerOfTwo) {
+ EXPECT_FALSE(IsPowerOfTwo(-1));
+ EXPECT_FALSE(IsPowerOfTwo(0));
+ EXPECT_TRUE(IsPowerOfTwo(1));
+ EXPECT_TRUE(IsPowerOfTwo(2));
+ // Unsigned 64 bit cases.
+ for (uint32_t i = 2; i < 64; i++) {
+ const uint64_t val = uint64_t{1} << i;
+ EXPECT_FALSE(IsPowerOfTwo(val - 1));
+ EXPECT_TRUE(IsPowerOfTwo(val));
+ EXPECT_FALSE(IsPowerOfTwo(val + 1));
+ }
+ // Signed 64 bit cases.
+ for (uint32_t i = 2; i < 63; i++) {
+ const int64_t val = int64_t{1} << i;
+ EXPECT_FALSE(IsPowerOfTwo(val - 1));
+ EXPECT_TRUE(IsPowerOfTwo(val));
+ EXPECT_FALSE(IsPowerOfTwo(val + 1));
+ }
+ // Signed integers with only the last bit set are negative, not powers of two.
+ EXPECT_FALSE(IsPowerOfTwo(int64_t{1} << 63));
+}
+
} // namespace bits
} // namespace base