What is std::__lg?

Question

As title I don't know what is std::__lg mean after google it?And what exactly this line do : int n = std::__lg(block_sz - pos_l + 1);

Answer 1

It's helper to compute the 2-based logarithm of integer number, i.e. it return the index of highest set bit in the number (or -1 for 0).

I.e. for 1 it will return 0, for 16 it will return 4, for 1024 it will return 10, etc.

This can be used to efficiently predict the pre-allocated size for arrays, round to the nearest power of 2 and thing like that.

Note, that as any other function starting with __, it's internal function of the compiler or the library, so you should not rely on its existence, such code wouldn't be portable. Other implementations of std library can come with completely solution and different names of similar helpers (if they use something similar at all).

POSIX provides similar function - ffs(), there are also ffsl and ffsll (see the same page) which is GNU extension and work with long and long long respectively.

For the question from comment - how to use it from Java. Because of the above it's not good idea first, secondly it would require JNI wrapper for this. And third but most important - there is no reason for this actually. Java already provides similar methods Integer.heghestOneBit(), although note it returns +1 in comparison to described std::__lg, i.e. 0 for 0, 1 for 1, 11 for 1024, etc.

Answer 2

It's an identifier used internally by your compiler (very likely GCC), because all identifiers with double underscores belong to the compiler implementation.

Nowhere in your own code should something like __lg be seen or used. Use the interface of the standard library, not its implementation. If your own code directly uses __lg, then you have no guarantee that the code will compile or do the right thing with any other compiler or even with any other version of the same compiler.

As the C++ standard says at §2.10 [lex.name]:

Each identifier that contains a double underscore __ or begins with an underscore followed by an uppercase letter is reserved to the implementation for any use.

As for what that GCC thing actually is, just look at the source code which a Google search for "std::__lg" turns up.

Depending on the actual types of block_sz and pos_l, it should be either this:

/// This is a helper function for the sort routines and for random.tcc.
//  Precondition: __n > 0.
template<typename _Size>
  inline _Size
  __lg(_Size __n)
  {
    _Size __k;
    for (__k = 0; __n != 0; __n >>= 1)
  ++__k;
    return __k - 1;
  }

Or this:

inline int
__lg(int __n)
{ return sizeof(int) * __CHAR_BIT__  - 1 - __builtin_clz(__n); }

Now, __CHAR_BIT__ is like the standard CHAR_BIT macro. As GCC documentation says:

Defined to the number of bits used in the representation of the char data type. It exists to make the standard header given numerical limits work correctly. You should not use this macro directly; instead, include the appropriate headers.

__builtin_clz is another GCC-specific function. Again, GCC documentation explains its purpose:

Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.

I think if you need such functionality, then it's trivial to write it yourself. In fact, the question is why you need it in the first place. The real answer to your actual problem probably lies in the code around the int n = std::__lg(block_sz - pos_l + 1); line.

---

Things to keep in mind:

• Do not use anything with two consecutive underscores in your own code.
• GCC is open source, so the internal implementation of special functions or macros is not secret but can easily be browsed online.