From f7ec2efe1923edf6365c04e3596a32d1b41d3a7f Mon Sep 17 00:00:00 2001
From: Yedidya Feldblum <yfeldblum@fb.com>
Date: Wed, 30 Aug 2017 11:39:43 -0700
Subject: [PATCH] constexpr_log2

Summary:
[Folly] `constexpr_log2`.

Useful for anything that needs to compute log2 at compile time.

Reviewed By: eduardo-elizondo

Differential Revision: D5734727

fbshipit-source-id: 8eab7991eea2104570eecd8e84ede6160bb0b549
---
 folly/portability/Constexpr.h            |  5 +++++
 folly/portability/test/ConstexprTest.cpp | 21 +++++++++++++++++++++
 2 files changed, 26 insertions(+)

diff --git a/folly/portability/Constexpr.h b/folly/portability/Constexpr.h
index 0b5c5a1a..a7620918 100644
--- a/folly/portability/Constexpr.h
+++ b/folly/portability/Constexpr.h
@@ -81,6 +81,11 @@ constexpr auto constexpr_abs(T t)
   return detail::constexpr_abs_helper<T>::go(t);
 }
 
+template <typename T>
+constexpr T constexpr_log2(T t) {
+  return t == T(1) ? T(0) : T(1) + constexpr_log2(t / T(2));
+}
+
 namespace detail {
 
 template <typename Char>
diff --git a/folly/portability/test/ConstexprTest.cpp b/folly/portability/test/ConstexprTest.cpp
index bb4b8bee..d2f6dbe3 100644
--- a/folly/portability/test/ConstexprTest.cpp
+++ b/folly/portability/test/ConstexprTest.cpp
@@ -71,3 +71,24 @@ TEST_F(ConstexprTest, constexpr_abs_double_negative) {
   EXPECT_EQ(17.5, a);
   EXPECT_TRUE((std::is_same<const double, decltype(a)>::value));
 }
+
+TEST_F(ConstexprTest, constexpr_log2_1) {
+  constexpr auto v = 1ull;
+  constexpr auto a = folly::constexpr_log2(v);
+  EXPECT_EQ(0ull, a);
+  EXPECT_TRUE((std::is_same<decltype(v), decltype(a)>::value));
+}
+
+TEST_F(ConstexprTest, constexpr_log2_2) {
+  constexpr auto v = 2ull;
+  constexpr auto a = folly::constexpr_log2(v);
+  EXPECT_EQ(1ull, a);
+  EXPECT_TRUE((std::is_same<decltype(v), decltype(a)>::value));
+}
+
+TEST_F(ConstexprTest, constexpr_log2_64) {
+  constexpr auto v = 64ull;
+  constexpr auto a = folly::constexpr_log2(v);
+  EXPECT_EQ(6ull, a);
+  EXPECT_TRUE((std::is_same<decltype(v), decltype(a)>::value));
+}
-- 
2.34.1