From ce15293f7537bb6ac4b0e9925aa1710b89af2e27 Mon Sep 17 00:00:00 2001
From: Michael Curtiss <mcurtiss@fb.com>
Date: Thu, 16 Aug 2012 22:31:16 -0700
Subject: [PATCH] isPowTwo

Summary:
a la Hacker's Delight.

Also, fix nonsensical nextPowTwo benchmark.

Test Plan: Added test and benchmark.

Reviewed By: tudorb@fb.com

FB internal diff: D551510
---
 folly/Bits.h            | 12 ++++++++++++
 folly/test/BitsTest.cpp | 37 +++++++++++++++++++++++++++++++++++--
 2 files changed, 47 insertions(+), 2 deletions(-)

diff --git a/folly/Bits.h b/folly/Bits.h
index 8ecac77c..3a05047d 100644
--- a/folly/Bits.h
+++ b/folly/Bits.h
@@ -32,6 +32,9 @@
  * nextPowTwo(x)
  *    Finds the next power of two >= x.
  *
+ * isPowTwo(x)
+ *    return true iff x is a power of two
+ *
  * Endian
  *    convert between native, big, and little endian representation
  *    Endian::big(x)      big <-> native
@@ -178,6 +181,15 @@ nextPowTwo(T v) {
   return 1ul << findLastSet(v - 1);
 }
 
+template <class T>
+inline
+typename std::enable_if<
+  std::is_integral<T>::value && std::is_unsigned<T>::value,
+  bool>::type
+isPowTwo(T v) {
+  return ((v != 0) && !(v & (v-1)));   // yes, this is endian-agnostic
+}
+
 /**
  * Population count
  */
diff --git a/folly/test/BitsTest.cpp b/folly/test/BitsTest.cpp
index 99bdcb48..8634246a 100644
--- a/folly/test/BitsTest.cpp
+++ b/folly/test/BitsTest.cpp
@@ -109,9 +109,42 @@ TEST(Bits, nextPowTwoClz) {
   testPowTwo(nextPowTwo);
 }
 
-int x; // prevent the loop from getting optimized away
 BENCHMARK(nextPowTwoClz, iters) {
-  x = folly::nextPowTwo(iters);
+  for (unsigned long i = 0; i < iters; ++i) {
+    auto x = folly::nextPowTwo(iters);
+    folly::doNotOptimizeAway(x);
+  }
+}
+
+TEST(Bits, isPowTwo) {
+  EXPECT_FALSE(isPowTwo(0u));
+  EXPECT_TRUE(isPowTwo(1ul));
+  EXPECT_TRUE(isPowTwo(2ull));
+  EXPECT_FALSE(isPowTwo(3ul));
+  EXPECT_TRUE(isPowTwo(4ul));
+  EXPECT_FALSE(isPowTwo(5ul));
+  EXPECT_TRUE(isPowTwo(8ul));
+  EXPECT_FALSE(isPowTwo(15u));
+  EXPECT_TRUE(isPowTwo(16u));
+  EXPECT_FALSE(isPowTwo(17u));
+  EXPECT_FALSE(isPowTwo(511ul));
+  EXPECT_TRUE(isPowTwo(512ul));
+  EXPECT_FALSE(isPowTwo(513ul));
+  EXPECT_FALSE(isPowTwo((1ul<<31) - 1));
+  EXPECT_TRUE(isPowTwo(1ul<<31));
+  EXPECT_FALSE(isPowTwo((1ul<<31) + 1));
+  EXPECT_FALSE(isPowTwo((1ull<<63) - 1));
+  EXPECT_TRUE(isPowTwo(1ull<<63));
+  EXPECT_FALSE(isPowTwo((1ull<<63) + 1));
+}
+
+BENCHMARK_DRAW_LINE();
+BENCHMARK(isPowTwo, iters) {
+  bool b;
+  for (unsigned long i = 0; i < iters; ++i) {
+    b = folly::isPowTwo(i);
+    folly::doNotOptimizeAway(b);
+  }
 }
 
 TEST(Bits, popcount) {
-- 
2.34.1