JDK-8349637 : Integer.numberOfLeadingZeros outputs incorrectly in certain cases
  • Type: Bug
  • Component: hotspot
  • Sub-Component: compiler
  • Affected Version: 19,21,24,25
  • Priority: P2
  • Status: Resolved
  • Resolution: Fixed
  • OS: generic
  • CPU: generic
  • Submitted: 2025-02-06
  • Updated: 2025-04-14
  • Resolved: 2025-03-03
The Version table provides details related to the release that this issue/RFE will be addressed.

Unresolved : Release in which this issue/RFE will be addressed.
Resolved: Release in which this issue/RFE has been resolved.
Fixed : Release in which this issue/RFE has been fixed. The release containing this fix may be available for download as an Early Access Release or a General Availability Release.

To download the current JDK release, click here.
JDK 21 JDK 24 JDK 25
21.0.8-oracleFixed 24.0.2Fixed 25 b13Fixed
Related Reports
Causes :  
Relates :  
Relates :  
Relates :  
Sub Tasks
JDK-8350430 :  
JDK-8350431 :  
Description
ADDITIONAL SYSTEM INFORMATION :
Windows 11 [Version 10.0.26100.2894]
JDK 21.0.6, 23.0.2, 24-ea+35, 25-ea+8

A DESCRIPTION OF THE PROBLEM :
Use numberOfLeadingZeros inside a short loop.
Use arrays for input, output, or both.
Access arrays sequentially.
Do not use branching statements such as if statements within the loop.
A certain number of loops (hundreds of thousands of times?).
Under these conditions, it may return a number that is 1 less at the boundary where the value changes.
Could the Intrinsic of Integer.numberOfLeadingZeros be causing the problem?

0x01FFFFFF: expected=7, actual=6
0x03FFFFFE-0x03FFFFFF: expected=6, actual=5
0x07FFFFFC-0x07FFFFFF: expected=5, actual=4
0x0FFFFFF8-0x0FFFFFFF: expected=4, actual=3
0x1FFFFFF0-0x1FFFFFFF: expected=3, actual=2
0x3FFFFFE0-0x3FFFFFFF: expected=2, actual=1

STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
var out = new int[0x2000004];
for (int i = 0; i < out.length; i++)
	out[i] = Integer.numberOfLeadingZeros(i);
System.out.println(out[0x1FFFFFF]);


---------- BEGIN SOURCE ----------
public class Main {
	public static void main(String[] args) {
		arrayOutput(0x01000000, 0x02000004);
		arrayOutput(0x03000000, 0x04000004);
		arrayOutput(0x07000000, 0x08000004);
		arrayOutput(0x0F000000, 0x10000004);
		arrayOutput(0x1F000000, 0x20000004);
		arrayOutput(0x3F000000, 0x40000004);
		System.out.println();

		for (int loop = 0; loop < 5; loop++) {
			arrayInput(0x200000);
		}
	}

	static void arrayOutput(int from, int to) {
		var output = new int[to - from];
		for (int i = from; i < to; i++) {
			output[i - from] = Integer.numberOfLeadingZeros(i);
		}

		for (int i = from; i < to; i++) {
			int nlz = Integer.numberOfLeadingZeros(i);
			if (nlz != output[i - from]) {
				System.out.printf("0x%08X: expected=%d actual=%d%n", i, nlz, output[i - from]);
			}
		}
	}

	static void arrayInput(int size) {
		int expected = 0;
		for (int i = 0; i < size; i++)
			expected += Integer.numberOfLeadingZeros(-1 >>> i);

		var input = new int[size];
		java.util.Arrays.setAll(input, i -> -1 >>> i);
		int actual = 0;
		for (int i = 0; i < size; i++)
			actual += Integer.numberOfLeadingZeros(input[i]);

		System.out.printf("expected=%d, actual=%d%n", expected, actual);
	}
}
---------- END SOURCE ----------


Comments
[jdk21u-fix-request] Approval Request from Paul Hohensee Backport for parity with Oracle 21.0.8. 24u fix request applies: Fixes an incorrect result of Integer.numberOfLeadingZeros. Fix is low risk (two lines) and there is a workaround (disable the intrinsic). Applies cleanly and was tested in JDK 25 for several days in the CI. More detail: Clean except for copyright in TestNumberOfContinuousZeros.java. Passes tier2 and the modified test. Low risk: algorithmically, it's zero risk, vis The algorithm works by converting the argument to a double and using the resulting exponent as the basis for the number of leading zeros in the argument: the exponent reflects the number of leading zeros because the fraction equals the argument shifted left until the highest set bit is implied by the fraction. The bug was that if the 2nd-to-highest bit is also set, the exponent may be off by one due to rounding up. The fix is to unconditionally clear the 2nd-to-highest argument bit by andn'ing the argument-shifted-right-by-1 with itself. andn is 1 iff the left is 0 and the right is 1, so the result is guaranteed to keep the high bit set because a zero is shifted into that position in the argument-shifted-right-by-1. It's also guaranteed to clear the 2nd-to-highest bit because the highest set bit in the argument-shifted-left-by-1 will be the left argument of the andn, so guaranteed to clear the 2nd-to-highest bit since the result of andn is always zero if its left argument is 1.
08-04-2025

A pull request was submitted for review. Branch: master URL: https://git.openjdk.org/jdk21u-dev/pull/1584 Date: 2025-04-03 13:37:04 +0000
03-04-2025

A pull request was submitted for review. Branch: master URL: https://git.openjdk.org/jdk24u/pull/118 Date: 2025-03-07 11:20:59 +0000
07-03-2025

Fix Request (JDK 24u): Fixes an incorrect result of Integer.numberOfLeadingZeros. Fix is low risk (two lines) and there is a workaround (disable the intrinsic). Applies cleanly and was tested in JDK 25 for several days in the CI.
07-03-2025

Changeset: 3657e92e Branch: master Author: Jasmine Karthikeyan <jkarthikeyan@openjdk.org> Date: 2025-03-03 05:18:55 +0000 URL: https://git.openjdk.org/jdk/commit/3657e92ead1e678942fcb272e77c3867eb5aa13e
03-03-2025

ILW = Incorrect result of Integer.numberOfLeadingZeros (regression in JDK 19), with large values and when used in a loop and C2's autovectorizer can optimize it, -XX:+UnlockDiagnosticVMOptions -XX:DisableIntrinsic=_numberOfLeadingZeros_i = HMM = P2
17-02-2025

I believe the vectorized output code for Long.numberOfLeadingZeros doesn't suffer from this issue because it uses a different approach to calculate the leading zeros, without relying on floating point semantics. Instead it calculates the the leading zeros more directly using a lookup table to find the zeros in each 4-bit segment, and then combining them. This implementation is shared with the versions for short and byte as well.
13-02-2025

We need to double check the intrinsic of Long.numberOfLeadingZeros to see if it has the same issue. More broadly check the enhancement for Integer/Long leading/trailing that was originally worked on the panama repo related to this issue https://bugs.openjdk.org/browse/JDK-8284459
13-02-2025

A pull request was submitted for review. Branch: master URL: https://git.openjdk.org/jdk/pull/23579 Date: 2025-02-12 05:47:52 +0000
12-02-2025

I had a look at this, and I believe the issue is due to a bug in the x86 implementation of CountLeadingZerosV for avx2 integers. In C2_MacroAssembler::vector_count_leading_zeros_int_avx, we convert the int value to a float, to calculate the leading zeros based on the float exponent. However, in the case where 2 int values have the same float representation we end up rounding up in some cases, leading to wrong bit calculation in some cases. This is most clearly seen in the case of 0x01FFFFFF, as (float)0x01FFFFFF == (float)0x02000000). I've added a reduced reproducer.
12-02-2025

I had some time and access to a Windows system, so I looked into this today. JDK 19 b25 build, which Andrew narrowed this down to, has several changes https://bugs.openjdk.org/issues/?jql=project%20%3D%20JDK%20AND%20fixVersion%20%3D%20%2219%22%20AND%20%22Resolved%20In%20Build%22%20%3D%20b25. But out of those changes, only a few appear remotely related and that's a good thing. I started by checking out ("git checkout -b <foo> <specific commit>") from a few select integrated issues from that list and then running the attached reproducer against that built JDK. It turns out that something in the change that went into https://bugs.openjdk.org/browse/JDK-8284960 is what's causing this issue. If I exclude that integrated commit from the JDK 19 source workspace and build a JDK, then the issue is no longer reproducible against that JDK. Given this, I'll change the "Caused by" link to point to this issue and also change the component from hotspot -> runtime to hotspot -> compiler (to match the component/sub-component of JDK-8284960)
11-02-2025

As far as I can see, there are several other changes that were part of JDK 19 b25 https://bugs.openjdk.org/issues/?jql=project%20%3D%20JDK%20AND%20fixVersion%20%3D%20%2219%22%20AND%20%22Resolved%20In%20Build%22%20%3D%20b25
07-02-2025

I found the the problem was introduced in JDK 19 b25 and JDK-8287384 is the only issue fixed in that build.
07-02-2025

Hello Andrew [~tongwan], this issue is linked to https://bugs.openjdk.org/browse/JDK-8287384 but that issue is just a test library related change and doesn't appear related to this. Did you mean to link this to some other issue?
07-02-2025

The observations on Windows 11: JDK 8, 11, and 17: Passed. JDK 19+24: Passed. JDK 19+25: Failed, incorrect values observed JDK 21, 23, 24, and 25: Failed.
07-02-2025