I need a Java equivalent of __builtin_clz.
It feels like the answer should be Long.numberOfLeadingZeros but they return completely different answers.
I'm starting to wonder if there is a low-level reason for this - maybe endianness? or some quirk of unsigned?
EDIT: False alarm. This is purely caused by a typo - the original code actually calls __builtin_ctzll and is matched by Long.numberOfTrailingZeros
Long.numberOfLeadingZeros is precisely correct.
The fact that you get different answers is because C. C does not define what int means. Therefore, the answer that __builtin_clz(a) gives is different on every box you run it on: It depends on the bit width of int, and as per the C standard, the bit width of an int is whatever is convenient for the system you're compiling for. If it's 32-bit (that's a very common bit width), __builtin_clz(16) would return 27. If it's 64-bit (also quite common), __builtin_clz(16) would return 59.
Java doesn't generally 'do' the whole undefined thing. In java, unlike C, int is a signed 32-bit number. No matter what VM, version, platform, or OS you're running it on or compiled it on. Similarly, a long is signed 64-bit.
Nevertheless, Long.numberOfLeadingZeroes effectively treats the number as unsigned just like __builtin_clz does: That means __builtin_clz(x), where x is a negative number, always returns 0 (or should, according to the C spec), and Long.numberOfLeadingZeros does the exact same thing: Always returns 0 (no leading zero bits), for negative numbers.
In other words, on 64-bit systems, __builtin_clz(x) is matched perfectly by Long.numberOfLeadingZeros(x) in java. On 32-bit systems, __builtin_clz(x) returns 32 less than that (__builtin_clz(16) on 64-bit is 59, but on 32-bit, it's 27), and in java, you'd have to use Integer.numberOfLeadingZeros() instead. Integer.numberOfLeadingZeros(16) returns 27. Just like __builtin_clz(16) would , if targeting a system where int is defined as 32-bit (it would be, if targeting 32-bit processors).
False alarm: Caused by a typo - I actually needed __builtin_ctzll instead, which now makes a lot more sense.
__builtin_clz() counts the number of leading zeroes in a non-zero int value. This number depends on the representation of type int, thus has not direct equivalent in java because the number of bits in C standard integer types such as int, long and long long is implementation defined, whereas the java specification fixes the size and representation of types int and long.
In addition to __builtin_clz(int), gcc defines __builtin_clzl(long) and __builtin_clzll(long long). On most current systems, the C ABI defines int with 32 bits and long long with 64 bits, making Integer.numberOfLeadingZeros(int) and Long.numberOfLeadingZeros(long) equivalent respectively to __builtin_clz and __builtin_clzll. Note however that the java functions have defined behavior for a zero argument which the C builtins do not have, as a consequence of their implementation as a single CPU instruction (on some architectures).
__builtin_ctz(int), __builtin_ctzl(long) and __builtin_ctzll(long long) count the number of trailing zeroes in a non-zero argument of the corresponding type. For a non zero value, the number of trailing zeroes only depends on the value of the argument, not its type size. The corresponding java methods are Integer.numberOfTrailingZeros(int) and Long.numberOfTrailingZeros(long). These methods are defined for all argument values and return 32 and 64 respectively for a zero argument.
