What does the code comment 'HD, Figure' mean in Java java.lang.Integer class?

Question

for example, the JDK method java.lang.Integer.numberOfLeadingZeros(int):

public static int numberOfLeadingZeros(int i) {
    // HD, Figure 5-6
    if (i == 0)
        return 32;
    int n = 1;
    if (i >>> 16 == 0) { n += 16; i <<= 16; }
    if (i >>> 24 == 0) { n +=  8; i <<=  8; }
    if (i >>> 28 == 0) { n +=  4; i <<=  4; }
    if (i >>> 30 == 0) { n +=  2; i <<=  2; }
    n -= i >>> 31;
    return n;
}

what does the code comment 'HD, Figure 5-6' mean?

Fragonard

It looks like a reference to literature – Rarely

Answer 1

HD = Hacker's Delight. See the the javadoc:

Implementation note: The implementations of the "bit twiddling" methods (such as highestOneBit and numberOfTrailingZeros) are based on material from Henry S. Warren, Jr.'s Hacker's Delight, (Addison Wesley, 2002).

Drummond

Cool man, I think I found the reason that why numberOfLeadingZeros() method does not have negative condition logic: if(i <0) return 0; I just download a pdf copy of the HD book, the code example in HD for numberOfLeadingZeros is:int ntz(unsigned x) { ...}, see? the param in HD book is unsigned, but in Java, it is int.I think the programmer who write the java code just copy the code from HD and forgot to optimized the negative condition of signed int param. – Fragonard

@Jason: I’m very sure that ntz means “number of trailing zeros” rather than “number of leading zeros”. – Milurd

@Milurd I miss spell it, the function name should be nlz(), here is the full copy from HD book: int nlz(unsigned x) { int n; if (x == 0) return(32); n = 1; if ((x >> 16) == 0) {n = n +16; x = x <<16;} if ((x >> 24) == 0) {n = n + 8; x = x << 8;} if ((x >> 28) == 0) {n = n + 4; x = x << 4;} if ((x >> 30) == 0) {n = n + 2; x = x << 2;} n = n - (x >> 31); return n; } – Fragonard

Answer 2

There are also such comments in java.lang.Long and java.lang.Math.

For example, the addExactmethod in java.lang.Math:

public static int addExact(int x, int y) {
    int r = x + y;
    // HD 2-12 Overflow iff both arguments have the opposite sign of the result
    if (((x ^ r) & (y ^ r)) < 0) {
        throw new ArithmeticException("integer overflow");
    }
    return r;
}

For information of Hacker's Delight we can also refer to: http://hackersdelight.org/

Gerfen