This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
[Patch] Use __builtin_clz* for __lg
- From: Paolo Carlini <pcarlini at suse dot de>
- To: libstdc++ <libstdc++ at gcc dot gnu dot org>
- Date: Wed, 24 Oct 2007 21:57:33 +0200
- Subject: [Patch] Use __builtin_clz* for __lg
Hi,
today, while working on something else, I noticed that we weren't
exploiting the various __builtin_clz* for our internal integer log2.
Seems a good idea to me, but please double check... Also, for the
generic case, I'm seeing a slightly tighter loop with the below tweak
(actually, that is apparently the most widespread way of implementing it).
Tested x86_64-linux.
Paolo.
////////////////
2007-10-24 Paolo Carlini <pcarlini@suse.de>
* include/bits/stl_algo.h (__lg<>(_Size)): Slightly tweak.
(__lg(int), __lg(long), __lg(long long)): Add, overloads
exploiting __builtin_clz*.
Index: include/bits/stl_algo.h
===================================================================
--- include/bits/stl_algo.h (revision 129604)
+++ include/bits/stl_algo.h (working copy)
@@ -2085,7 +2085,7 @@
/**
* @if maint
- * This is a helper function for the sort routines.
+ * This is a helper function for the sort routines. Precondition: __n > 0.
* @endif
*/
template<typename _Size>
@@ -2093,11 +2093,23 @@
__lg(_Size __n)
{
_Size __k;
- for (__k = 0; __n != 1; __n >>= 1)
+ for (__k = 0; __n != 0; __n >>= 1)
++__k;
- return __k;
+ return __k - 1;
}
+ inline int
+ __lg(int __n)
+ { return sizeof(int) * __CHAR_BIT__ - 1 - __builtin_clz(__n); }
+
+ inline long
+ __lg(long __n)
+ { return sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); }
+
+ inline long long
+ __lg(long long __n)
+ { return sizeof(long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); }
+
// sort
template<typename _RandomAccessIterator, typename _Size>