public static int ntz ( long val ) { // A full binary search to determine the low byte was slower than // a linear search for nextSetBit(). This is most likely because // the implementation of nextSetBit() shifts bits to the right, increasing // the probability that the first non-zero byte is in the rhs. // // This implementation does a single binary search at the top level only // so that all other bit shifting can be done on ints instead of longs to // remain friendly to 32 bit architectures. In addition, the case of a // non-zero first byte is checked for first because it is the most common // in dense bit arrays. int lower = ( int ) val ; int lowByte = lower & 0xff ; if ( lowByte != 0 ) return ntzTable [ lowByte ] ; if ( lower != 0 ) { lowByte = ( lower >>> 8 ) & 0xff ; if ( lowByte != 0 ) return ntzTable [ lowByte ] + 8 ; lowByte = ( lower >>> 16 ) & 0xff ; if ( lowByte != 0 ) return ntzTable [ lowByte ] + 16 ; // no need to mask off low byte for the last byte in the 32 bit word // no need to check for zero on the last byte either. return ntzTable [ lower >>> 24 ] + 24 ; } else { // grab upper 32 bits int upper = ( int ) ( val >> 32 ) ; lowByte = upper & 0xff ; if ( lowByte != 0 ) return ntzTable [ lowByte ] + 32 ; lowByte = ( upper >>> 8 ) & 0xff ; if ( lowByte != 0 ) return ntzTable [ lowByte ] + 40 ; lowByte = ( upper >>> 16 ) & 0xff ; if ( lowByte != 0 ) return ntzTable [ lowByte ] + 48 ; // no need to mask off low byte for the last byte in the 32 bit word // no need to check for zero on the last byte either. return ntzTable [ upper >>> 24 ] + 56 ; } }
Returns number of trailing zeros in a 64 bit long value .