Java-Bitscan
Home * Board Representation * Bitboards * BitScan * Java-Bitscan
Java 1.5 has Long.numberOfTrailingZeros which might be the preferred one for bitScanForward. Long.numberOfLeadingZeros is suited to replace bitScanReverse xor 63.
Source Samples
Some ports from C-source:
/** * @author Gerd Isenberg * @return index 0..63 of LS1B -1023 if passing zero * @param b a 64-bit word to bitscan */ static public int bitScanForwardDbl(long b) { double x = (double)(b & - b); int exp = (int) (Double.doubleToLongBits(x) >>> 52); return (exp & 2047) - 1023; }
/** * @author Matt Taylor * @return index 0..63 * @param bb a 64-bit word to bitscan, should not be zero */ static private final int[] foldedTable = { 63,30, 3,32,59,14,11,33, 60,24,50, 9,55,19,21,34, 61,29, 2,53,51,23,41,18, 56,28, 1,43,46,27, 0,35, 62,31,58, 4, 5,49,54, 6, 15,52,12,40, 7,42,45,16, 25,57,48,13,10,39, 8,44, 20,47,38,22,17,37,36,26, }; static public int bitScanForwardMatt(long b) { b ^= (b - 1); int folded = ((int)b) ^ ((int)(b >>> 32)); return foldedTable[(folded * 0x78291ACF) >>> 26]; }
/** * @author Charles E. Leiserson * Harald Prokop * Keith H. Randall * "Using de Bruijn Sequences to Index a 1 in a Computer Word" * @return index 0..63 * @param bb a 64-bit word to bitscan, should not be zero */ static private final long deBruijn = 0x03f79d71b4cb0a89L; static private final int[] magicTable = { 0, 1,48, 2,57,49,28, 3, 61,58,50,42,38,29,17, 4, 62,55,59,36,53,51,43,22, 45,39,33,30,24,18,12, 5, 63,47,56,27,60,41,37,16, 54,35,52,21,44,32,23,11, 46,26,40,15,34,20,31,10, 25,14,19, 9,13, 8, 7, 6, }; static public int bitScanForwardDeBruijn64 (long b) { int idx = (int)(((b & -b) * deBruijn) >>> 58); return magicTable[idx]; }
/** * @author Gerd Isenberg * @return index 0..63 of MS1B -1023 if passing zero * @param bb a 64-bit word to bitscan */ static public int bitScanReverse(long bb) { double x = (double)(bb & ~(bb >>> 32)); int exp = (int) (Double.doubleToLongBits(x) >> 52); int sign = (exp >> 11) & 63; // 63 if < 0 else 0 exp = (exp & 2047)-1023; return exp | sign; }