Index: include/algorithm
===================================================================
--- include/algorithm
+++ include/algorithm
@@ -752,29 +752,17 @@
 
 // Perform division by two quickly for positive integers (llvm.org/PR39129)
 
-template <typename _Integral>
-_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
-typename enable_if
-<
-    is_integral<_Integral>::value,
-    _Integral
->::type
-__half_positive(_Integral __value)
+template <typename T, typename = void>
+struct __unsigned_len_type
 {
-    return static_cast<_Integral>(static_cast<typename make_unsigned<_Integral>::type>(__value) / 2);
-}
+    typedef T type;
+};
 
-template <typename _Tp>
-_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
-typename enable_if
-<
-    !is_integral<_Tp>::value,
-    _Tp
->::type
-__half_positive(_Tp __value)
+template <typename _Integral>
+struct __unsigned_len_type<_Integral, typename enable_if<is_integral<_Integral>::value>::type>
 {
-    return __value / 2;
-}
+    typedef typename make_unsigned<_Integral>::type type;
+};
 
 #ifdef _LIBCPP_DEBUG
 
@@ -3225,10 +3213,11 @@
 partition_point(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
 {
     typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
-    difference_type __len = _VSTD::distance(__first, __last);
+    typedef typename __unsigned_len_type<difference_type>::type __len_type;
+    __len_type __len = static_cast<__len_type>(_VSTD::distance(__first, __last));
     while (__len != 0)
     {
-        difference_type __l2 = _VSTD::__half_positive(__len);
+        __len_type __l2 = __len / 2;
         _ForwardIterator __m = __first;
         _VSTD::advance(__m, __l2);
         if (__pred(*__m))
@@ -4092,10 +4081,11 @@
 __lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
 {
     typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
-    difference_type __len = _VSTD::distance(__first, __last);
+    typedef typename make_unsigned<difference_type>::type __len_type;
+    __len_type __len = _VSTD::distance(__first, __last);
     while (__len != 0)
     {
-        difference_type __l2 = _VSTD::__half_positive(__len);
+        __len_type __l2 = __len / 2;
         _ForwardIterator __m = __first;
         _VSTD::advance(__m, __l2);
         if (__comp(*__m, __value_))
@@ -4134,10 +4124,11 @@
 __upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
 {
     typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
-    difference_type __len = _VSTD::distance(__first, __last);
+    typedef typename __unsigned_len_type<difference_type>::type __len_type;
+    __len_type __len = static_cast<__len_type>(_VSTD::distance(__first, __last));
     while (__len != 0)
     {
-        difference_type __l2 = _VSTD::__half_positive(__len);
+        __len_type __l2 = __len / 2;
         _ForwardIterator __m = __first;
         _VSTD::advance(__m, __l2);
         if (__comp(__value_, *__m))
@@ -4176,10 +4167,11 @@
 __equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
 {
     typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
-    difference_type __len = _VSTD::distance(__first, __last);
+    typedef typename __unsigned_len_type<difference_type>::type __len_type;
+    __len_type __len = static_cast<__len_type>(_VSTD::distance(__first, __last));
     while (__len != 0)
     {
-        difference_type __l2 = _VSTD::__half_positive(__len);
+        __len_type __l2 = __len / 2;
         _ForwardIterator __m = __first;
         _VSTD::advance(__m, __l2);
         if (__comp(*__m, __value_))
Index: test/libcxx/algorithms/half_positive.pass.cpp
===================================================================
--- test/libcxx/algorithms/half_positive.pass.cpp
+++ /dev/null
@@ -1,59 +0,0 @@
-//===----------------------------------------------------------------------===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is dual licensed under the MIT and the University of Illinois Open
-// Source Licenses. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-
-// <algorithm>
-
-// template <typename _Tp> _Tp __half_positive(const _Tp&);
-
-// __half_positive divide integer number by 2 as unsigned number
-// if it's safe to do so. It can be an important optimization for lower bound,
-// for example.
-
-#include <algorithm>
-#include <cassert>
-#include <limits>
-#include <type_traits>
-
-#include "test_macros.h"
-#include "user_defined_integral.hpp"
-
-namespace {
-
-template <class IntType, class UnderlyingType = IntType>
-TEST_CONSTEXPR bool test(IntType max_v = IntType(std::numeric_limits<UnderlyingType>::max())) {
-    return std::__half_positive(max_v) == max_v / 2;
-}
-
-}  // namespace
-
-int main()
-{
-    {
-        assert(test<char>());
-        assert(test<int>());
-        assert(test<long>());
-        assert((test<UserDefinedIntegral<int>, int>()));
-        assert(test<size_t>());
-#if !defined(_LIBCPP_HAS_NO_INT128)
-        assert(test<__int128_t>());
-#endif  // !defined(_LIBCPP_HAS_NO_INT128)
-    }
-
-#if TEST_STD_VER >= 11
-    {
-        static_assert(test<char>(), "");
-        static_assert(test<int>(), "");
-        static_assert(test<long>(), "");
-        static_assert(test<size_t>(), "");
-#if !defined(_LIBCPP_HAS_NO_INT128)
-        static_assert(test<__int128_t>(), "");
-#endif  // !defined(_LIBCPP_HAS_NO_INT128)
-    }
-#endif // TEST_STD_VER >= 11
-}
Index: test/libcxx/algorithms/unsigned_len_type.pass.cpp
===================================================================
--- /dev/null
+++ test/libcxx/algorithms/unsigned_len_type.pass.cpp
@@ -0,0 +1,47 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <algorithm>
+
+// template <typename _Tp> _Tp __unsigned_len_type(const _Tp&);
+
+// __unsigned_len_type is used by algorithms to divide len by 2 faster.
+
+#include <algorithm>
+#include <cassert>
+#include <limits>
+#include <type_traits>
+
+#include "test_macros.h"
+#include "user_defined_integral.hpp"
+
+namespace {
+
+template <class In, class Out = typename std::make_unsigned<In>::type>
+TEST_CONSTEXPR bool test()
+{
+#if TEST_STD_VER >= 11
+    static_assert(std::is_same<typename std::__unsigned_len_type<In>::type, Out>::value, "");
+#endif // TEST_STD_VER >= 11
+    return std::is_same<typename std::__unsigned_len_type<In>::type, Out>::value;
+}
+
+}  // namespace
+
+int main()
+{
+    assert(test<char>());
+    assert(test<int>());
+    assert(test<long>());
+    assert(test<size_t>());
+    assert((test<UserDefinedIntegral<int>, UserDefinedIntegral<int> >()));
+#if !defined(_LIBCPP_HAS_NO_INT128)
+    assert(test<__int128_t>());
+#endif  // !defined(_LIBCPP_HAS_NO_INT128)
+}