0

Possible Duplicate:
How does Java handle integer underflows and overflows and how would you check for it?
Multiplication of two int’s gets negativ

My program is an implementation of a bloom filter. However, when I'm storing my hash function results in the bit array, the function (of the form f(i) = (a*i + b) % m where a, b, i, m are all positive integers) is giving me a negative result. The problem seems to be in the calculation of a*i which is coming out to be negative.

Ignore the print statements in the code; those were for debugging. Basically, the value of temp in this block of code is coming out to be negative and so I'm getting an ArrayOutOfBoundsException.

m is the bit array length, z is the number of hash functions being used, S is the set of values which are members of this bloom filter and H stores the values of a and b for the hash functions f1, f2, ..., fz.

public static int[] makeBitArray(int m, int z, ArrayList<Integer> S, int[] H)
{
    int[] C = new int[m];
    for (int i = 0; i < z; i++)
    {
        for (int q = 0; q < S.size() ; q++)
        {
            System.out.println(H[2*i]);
            int temp = S.get(q)*(H[2*i]);
            System.out.println(temp);
            System.out.println(S.get(q));
            System.out.println(H[2*i + 1]);
            System.out.println(m);
            int t = ((H[2*i]*S.get(q)) + H[2*i + 1])%m;
            System.out.println(t);
            C[t] = 1;
        }
    }
    return C;
}
Community
  • 1
  • 1
krandiash
  • 165
  • 3
  • 11

2 Answers2

2

Depending on how large the numbers m and z will be it might suffice to use a long. If you need larger numbers, consider a class such as BigInteger.

Johan Sjöberg
  • 47,929
  • 21
  • 130
  • 148
  • Good old numerical overflow. You've produced a value larger than Integer.MAX_VALUE. Tntegers are represented in two's complement, and your operation ends up flipping the high order bit from 0 (positive number) to 1 (negative number), thus causing the issue. Unfortunately, java does not give any indication to you that this happened. – Matt Sep 30 '12 at 17:46
0

Use long. (http://en.wikipedia.org/wiki/Integer_overflow)

Jiri Kremser
  • 12,471
  • 7
  • 45
  • 72
  • FYI Such short and snappy answers are frowned upon on SO and liable to downvotes (whether correct or not). If this is all you have to say, you should use the comment facility. – Marko Topolnik Sep 30 '12 at 10:19
  • Sometimes less is more, but in general I agree. – Jiri Kremser Sep 30 '12 at 10:44
  • Both the snappy advice and the link are probably helpful to OP, but answers should aim for a generally recognizable contribution. The contribution should be self-contained and not hiding behind a link---links are to be used only as references backing your claims. Note that I'm just passing along the lore, not criticizing you. I went through the same newbie process earlier this year :) When you get downvoted for a factually correct and, in your mind, helpful answer, it feels sore, so you learn how to avoid it :) – Marko Topolnik Sep 30 '12 at 10:51