Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-8225397

Integer value miscalculation in toString() method of BitSet

XMLWordPrintable

    • b25
    • generic
    • generic
    • Verified

        ADDITIONAL SYSTEM INFORMATION :
        Windows 10 Pro.
        Runtime information: Java(TM) SE Runtime Environment (build 1.8.0_172-b11).
        Code is also available in OpenJDK / jdk / jdk12
        view src/java.base/share/classes/java/util/BitSet.java

        A DESCRIPTION OF THE PROBLEM :
        StringBuilder instance creation in toString method of BitSet.
        StringBuilder b = new StringBuilder(6*numBits + 2)
        When we have more than 357913940 set bit(numBits) in BitSet then "6*numBits + 2" calculation exceeds the integer range and integer value spin it back to negative number.
        That leads to NegativeArraySizeException and BitSet value representation breaks.


        STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
        Set BitSet value more than 357913940.
        Call set() method more than 357913940 times, in every set() call, passed value in set() should be distinct.

        EXPECTED VERSUS ACTUAL BEHAVIOR :
        EXPECTED -
        Every set value in BitSet should be printed/represented by toString() method.
        ACTUAL -
        Exception in thread "main" java.lang.NegativeArraySizeException
        at java.lang.AbstractStringBuilder.<init>(AbstractStringBuilder.java:68)
        at java.lang.StringBuilder.<init>(StringBuilder.java:101)
        at java.util.BitSet.toString(BitSet.java:1186)
        at java.lang.String.valueOf(String.java:2994)
        at java.lang.StringBuilder.append(StringBuilder.java:131)

        ---------- BEGIN SOURCE ----------
        import java.util.BitSet;

        public class Eratosthenes {

            public BitSet sieveNumber(int n) {
                BitSet primeSet = new BitSet(n);

                for(int p =2; p*p <= n && p*p > 2; p++) {
                    if(primeSet.get(p) && p != 2) {
                        continue;
                    }

                    for(int i = p*2; i < n && i > 1; i = i + p) {
                        primeSet.set(i);
                    }
                }

                return primeSet;
            }


            public static void main(String[] arg) {
                Eratosthenes era = new Eratosthenes();
                BitSet primeSet = era.sieveNumber(2147483647);

                System.out.println("Cardinality : " + primeSet.cardinality());
                System.out.println("Prime set : " + primeSet);

                for(int i = 2; i < primeSet.length(); i++) {
                    if(!primeSet.get(i) && i > 2147483620) {
                        System.out.println(" " + i);
                    }
                }
            }
        }
        ---------- END SOURCE ----------

        CUSTOMER SUBMITTED WORKAROUND :
        Not right now.
        As of now only thought.
        Number 6 has been chosen carefully to represent index value of set bit but when numBits exceed 357913940, we can do segmentation of index value in multiple halves and then traverse individuals one by one.

        FREQUENCY : occasionally


              igerasim Ivan Gerasimov
              webbuggrp Webbug Group
              Votes:
              0 Vote for this issue
              Watchers:
              4 Start watching this issue

                Created:
                Updated:
                Resolved: