changeset 50795:5afedc9e4662

8203352: Improve java implementation of Integer/Long.numberOfLeadingZeros Reviewed-by: martin, igerasim Contributed-by: ivan.gerasimov@oracle.com, claes.redestad@oracle.com
author redestad
date Tue, 22 May 2018 14:44:18 +0200
parents afb9bc5328a3
children c4800cdd45c7
files src/java.base/share/classes/java/lang/Integer.java src/java.base/share/classes/java/lang/Long.java test/jdk/java/lang/Integer/BitTwiddle.java test/jdk/java/lang/Long/BitTwiddle.java
diffstat 4 files changed, 35 insertions(+), 31 deletions(-) [+]
line wrap: on
line diff
--- a/src/java.base/share/classes/java/lang/Integer.java	Tue May 22 05:20:48 2018 -0400
+++ b/src/java.base/share/classes/java/lang/Integer.java	Tue May 22 14:44:18 2018 +0200
@@ -1618,16 +1618,15 @@
      */
     @HotSpotIntrinsicCandidate
     public static int numberOfLeadingZeros(int i) {
-        // HD, Figure 5-6
+        // HD, Count leading 0's
         if (i <= 0)
             return i == 0 ? 32 : 0;
-        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;
+        int n = 31;
+        if (i >= 1 << 16) { n -= 16; i >>>= 16; }
+        if (i >= 1 <<  8) { n -=  8; i >>>=  8; }
+        if (i >= 1 <<  4) { n -=  4; i >>>=  4; }
+        if (i >= 1 <<  2) { n -=  2; i >>>=  2; }
+        return n - (i >>> 1);
     }
 
     /**
--- a/src/java.base/share/classes/java/lang/Long.java	Tue May 22 05:20:48 2018 -0400
+++ b/src/java.base/share/classes/java/lang/Long.java	Tue May 22 14:44:18 2018 +0200
@@ -1761,18 +1761,9 @@
      */
     @HotSpotIntrinsicCandidate
     public static int numberOfLeadingZeros(long i) {
-        // HD, Figure 5-6
-         if (i <= 0)
-            return i == 0 ? 64 : 0;
-        int n = 1;
         int x = (int)(i >>> 32);
-        if (x == 0) { n += 32; x = (int)i; }
-        if (x >>> 16 == 0) { n += 16; x <<= 16; }
-        if (x >>> 24 == 0) { n +=  8; x <<=  8; }
-        if (x >>> 28 == 0) { n +=  4; x <<=  4; }
-        if (x >>> 30 == 0) { n +=  2; x <<=  2; }
-        n -= x >>> 31;
-        return n;
+        return x == 0 ? 32 + Integer.numberOfLeadingZeros((int)i)
+                : Integer.numberOfLeadingZeros(x);
     }
 
     /**
--- a/test/jdk/java/lang/Integer/BitTwiddle.java	Tue May 22 05:20:48 2018 -0400
+++ b/test/jdk/java/lang/Integer/BitTwiddle.java	Tue May 22 14:44:18 2018 +0200
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2003, 2017, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2003, 2018, Oracle and/or its affiliates. All rights reserved.
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  *
  * This code is free software; you can redistribute it and/or modify it
@@ -83,6 +83,8 @@
             throw new RuntimeException("i");
         if (numberOfLeadingZeros(1) != (SIZE - 1))
             throw new RuntimeException("j");
+        if (numberOfLeadingZeros(Integer.MAX_VALUE) != 1)
+            throw new RuntimeException("lzmax");
 
         if (numberOfTrailingZeros(0) != SIZE)
             throw new RuntimeException("k");
@@ -96,6 +98,13 @@
             if (numberOfLeadingZeros(x) != numberOfTrailingZeros(reverse(x)))
                 throw new RuntimeException("n: " + toHexString(x));
         }
+        for (int i = 1, r = SIZE - 1; i != 0; i <<= 1, r--) {
+            if (numberOfLeadingZeros(i) != r ||
+                numberOfTrailingZeros(i) != (SIZE - r - 1) ||
+                numberOfLeadingZeros(i) != numberOfTrailingZeros(reverse(i))) {
+                throw new RuntimeException("lzx: " + toHexString(i));
+            }
+        }
 
         if (bitCount(0) != 0)
                 throw new RuntimeException("o");
@@ -152,11 +161,8 @@
         }
     }
 
+    private static final String ZEROS = "0".repeat(32);
     private static String leftpad(String s, int width) {
-        String r = s;
-        for (int c = 0; c < width - s.length(); c++) {
-            r = "0" + r;
-        }
-        return r;
+        return ZEROS.substring(0, width - s.length()) + s;
     }
 }
--- a/test/jdk/java/lang/Long/BitTwiddle.java	Tue May 22 05:20:48 2018 -0400
+++ b/test/jdk/java/lang/Long/BitTwiddle.java	Tue May 22 14:44:18 2018 +0200
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2003, 2017, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2003, 2018, Oracle and/or its affiliates. All rights reserved.
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  *
  * This code is free software; you can redistribute it and/or modify it
@@ -83,6 +83,10 @@
             throw new RuntimeException("i");
         if (numberOfLeadingZeros(1) != (SIZE - 1))
             throw new RuntimeException("j");
+        if (numberOfLeadingZeros(Long.MAX_VALUE) != 1)
+            throw new RuntimeException("lzmax");
+        if (numberOfLeadingZeros(Integer.MAX_VALUE + 1L) != (SIZE - 32))
+            throw new RuntimeException("lz32");
 
         if (numberOfTrailingZeros(0) != SIZE)
             throw new RuntimeException("k");
@@ -96,6 +100,13 @@
             if (numberOfLeadingZeros(x) != numberOfTrailingZeros(reverse(x)))
                 throw new RuntimeException("n: " + toHexString(x));
         }
+        for (long i = 1, r = SIZE - 1; i != 0; i <<= 1, r--) {
+            if (numberOfLeadingZeros(i) != (int)r ||
+                numberOfTrailingZeros(i) != (SIZE - (int)r - 1) ||
+                numberOfLeadingZeros(i) != numberOfTrailingZeros(reverse(i))) {
+                throw new RuntimeException("lzx: " + toHexString(i));
+            }
+        }
 
         if (bitCount(0) != 0)
                 throw new RuntimeException("o");
@@ -152,11 +163,8 @@
         }
     }
 
+    private static final String ZEROS = "0".repeat(64);
     private static String leftpad(String s, int width) {
-        String r = s;
-        for (int c = 0; c < width - s.length(); c++) {
-            r = "0" + r;
-        }
-        return r;
+        return ZEROS.substring(0, width - s.length()) + s;
     }
 }