The FindBugs Blog

Saturday, September 16, 2006

Is Math.abs broken?

You'd think that Math.abs would return a non-negative integer. You'd be wrong. In fact, Math.abs(Integer.MIN_VALUE) = Integer.MIN_VALUE. The problem is that Integer.MIN_VALUE is -2147483648, and +2147483648 cannot be represented as a 32-bit signed integer (Integer.MAX_VALUE = 2147483647).
How can this bite you? It is not uncommon to see code such as

Object x = bucket[ Math.abs(y.hashCode()) % bucket.length]

Why is the call to Math.abs there? Because essentially all processors implement integer division as rounding towards zero, rather than towards negative infinity (as most mathmeticians and computer scientists would prefer). Java defines integer division the same way. As a result, a remainder computation can give a negative result if the dividend is negative (e.g., (-3)%2 == -1).

If we had just written
Object x = bucket[ y.hashCode() % bucket.length]
then roughly half the time, the remainder would be negative and we'd get an array index out of bound exception. So people will call Math.abs to obtain a non-negative dividend.
But as we've discussed, Math.abs doesn't guarantee a non-negative dividend. if the hashCode is Integer.MIN_VALUE, then the result of the Math.abs will be negative and we will likely get a negative remainder and in array index out of bounds exception. The same pattern/problem comes up when using random 32 bit signed integers rather than hashCodes.

I'm not sure whether to be relieved or worried that this problem would occur only about one time out of 4 billion. An error that occurs half the time is a lot easier to find via testing. An error that comes up once out of 4 billion will be almost impossible to reproduce or find through testing.

FindBugs 1.1 searches for this bug pattern. How often do we find it?

  • 7 times in eclipse-SDK-3.2-solaris-gtk
  • 6 times in jboss-4.0.2
  • 6 times in eclipse-SDK-3.2-solaris-gtk
  • twice in tomcat-4.1.31
  • 9 times in BEA Weblogic 9.0
  • 10 times in IBM WebSphere 6.0.3

The (quick) recommended way to fix this simply use a integer bitwise and to clear the high bit, ensuring that the result is non-negative.

Object x = bucket[ (y.hashCode() & Integer.MAX_VALUE) % bucket.length]

If you know that the length of the array is a power of two, you can also use:
Object x = bucket[ y.hashCode() & ( bucket.length - 1) ]
One quick word of warning: you might not want to assume that the hashCode function gives uniformly distributed values. Sun's HashMap using the following method to stir the bits of a hashCode to try to ensure a more uniformly distributed hash value:

* Returns a hash value for the specified object. In addition to
* the object's own hashCode, this method applies a "supplemental
* hash function," which defends against poor quality hash functions.
* This is critical because HashMap uses power-of two length
* hash tables.

* The shift distances in this function were chosen as the result
* of an automated search over the entire four-dimensional search space.
static int hash(Object x) {
int h = x.hashCode();
h += ~(h << 9);
h ^= (h >>> 14);
h += (h << 4);
h ^= (h >>> 10);
return h;

So, back to my original question: Is Math.abs broken? I'm not sure how it could be any different. There isn't any value that could be returned for Math.abs(Integer.MIN_VALUE) that would be correct. And making Math.abs(Integer.MIN_VALUE) throw exception wouldn't really improve the situation. So I wouldn't say it is broken; just dangerous.

Bill Pugh


At 10:02 AM, Blogger jojava said...

> Object x = bucket[ Math.abs(y.hashCode()) % bucket.length];

i would suggest the following "fix"

Object x = bucket[ Math.abs(y.hashCode() % bucket.length)];

At 9:56 PM, Blogger behdad said...

Except that it would bill the '0' bucket twice as much as other buckets.

At 12:06 AM, Blogger Tony said...

Your stats can't be right:
7 times in eclipse-SDK-3.2-solaris-gtk
6 times in jboss-4.0.2
6 times in eclipse-SDK-3.2-solaris-gtk

Did you mean to have a difference between the 1st and 3rd packages names?

At 3:15 AM, Blogger tercumenette said...


At 3:15 AM, Blogger tercumenette said...


At 10:17 PM, Blogger quangntenemy said...

Cool thing! Gotta reuse it somewhere :)

At 6:48 AM, Blogger yazar said...

thank you very muchmedyum

At 4:03 AM, Anonymous Anonymous said...


At 4:32 AM, Anonymous Anonymous said...

Burun Estetiği

At 8:14 PM, Blogger women said...

Thanks admin moda

At 1:32 AM, Blogger Keep said...

Hello, please check out six pack ab and also six pack ab now

At 4:44 AM, Blogger Ak Sağlık said...

A very nice page. I think the effort has passed, we have to thank you:))
Göğüs küçültme

At 1:12 PM, Blogger valjok said...

Your statement that there is no positive for Integer.MIN_VALUE is based on a common belief that: the range of integers that can be represented in 32 bits is -2,147,483,648 to 2,147,483,647.

Actually, those who design the language could interpret the sign conversely. Then, we would have more positives so that there is always one for any negative :)

At 1:36 AM, Blogger city said...

thanks for share......

At 4:01 AM, Anonymous Anonymous said...

These information really worth saying, i think you are master of the content and thank you so much sharing that valuable information.
CCNA Training in Chennai

At 6:27 AM, Blogger Nainika Joseph said...

This article creates a new hope and inspiration with in me. Thanks for sharing article like this. The way you have stated everything above is quite awesome. Keep blogging like this. Thanks.

SAP training in Chennai

At 4:57 AM, Blogger Rohith said...

Great post....Thank you for posting the great content……I found it quiet interesting, hopefully you will keep posting such blogs…
If you Want more seo course in chennai

At 9:20 AM, Blogger Suseela Susiee said...

Great and useful article. Creating content regularly is very tough. Your points are motivated me to move on.

SEO Company in Chennai

At 6:21 AM, Blogger Nikithar said...

Great post....Thank you for posting the great content……I found it quiet interesting, hopefully you will keep posting such blogs…
If you Want more seo course chennai

At 7:38 AM, Blogger Sathya G said...

thank you for sharing such a nice and interesting blog with us. hope it might be much useful for us. keep on updating...
SEO Company In Chennai

At 3:54 AM, Blogger Yulianti Yuli said...

Cara Menurunkan Trombosit Tinggi
Cara Menurunkan Leukosit Tinggi Pada Anak
Obat Penyakit Kulit Scabies Yang Tersedia Di Apotik

At 5:43 AM, Blogger Sathya G said...

This is an awesome post.Really very informative and creative contents. These concept is a good way to enhance the knowledge.I like it and help me to development very well.Thank you for this brief explanation and very nice information.
Selenium Training in Chennai

At 3:11 AM, Blogger Nabila Fajri said...

Obat Fistula Ani
Cara Cepat Mengeringkan Luka Bakar
Obat Penghilang Bekas Luka
Obat Penghilang Bekas Luka Di Apotik
Nama Obat Gonore Kencing Nanah Di Apotik

At 9:11 AM, Blogger sunilkumarkuppam said...

This article is so informatic and it really helped me to know more about the Selenium Testing. So keep updating the content regularly.
Selenium Training in Chennai | Selenium Training | Selenium Course in Chennai

At 5:44 AM, Blogger Karthika Shree said...

Finding the time and actual effort to create a superb article like this is great thing. I’ll learn many new stuff right here! Good luck for the next post buddy..
Java Training in Chennai

At 9:05 AM, Blogger jenny Honey said...

Thanks for sharing this article, really helpful
Web Design Company in Hyderabad
SEO Company in Hyderabad

At 12:44 AM, Blogger sunitha vishnu said...

It is amazing and wonderful to visit your site.Thanks for sharing this information,this is useful to me...
Android Training in Chennai
Ios Training in Chennai

At 12:38 PM, Blogger Freddie King said...

mcdonaldsgutscheine | startlr | saludlimpia

At 11:26 PM, Blogger bava mahe said...

This article is so information and it really helped me to know more about the Selenium Testing. So keep updating the content regularly.
cloud computing training in chennai

At 1:04 AM, Blogger Ancy merina said...

Your posts is really helpful for me.Thanks for your wonderful post. I am very happy to read your post.
Web developers in bangalore
Website Design and Development Companies in Bangalore
ECommerce Web Design Company in bangalore
Outsource magento ecommerce services india

At 2:20 AM, Blogger CIIT Noida said...

What a wonderfull post! thank you... read with pleasure!

Best Linux training in Noida
Linux Training Institute in Noida

At 2:26 AM, Blogger CIIT Noida said...

Thank you for your post, I look for such article along time, today i find it finally. this post give me lots of advise it is very useful for me.

Best bca college in noida
Top bca colleges in noida

At 2:52 AM, Blogger smriti nayan said...

nice information thanks for giving this article
6 weeks CCNA Summer Internship
Best 6 weeks MCSE summer internship

At 1:35 AM, Blogger Harminder Singh said...

Indian Cyber Army is now coming up with Summer Internship in “Ethical hacking & Cyber Crime Investigation”. Candidates have to get themselves registered to be a part of this Summer Internship program starting from 15th June. Here you will acknowledge the tact to observe cyber crime and tricks to fight against it. The internship content is especially designed by Indian Cyber Army’s expert for aspiring hackers and cyber security geeks.

At 5:46 AM, Blogger preeti verma said...

Best M Tech Colleges in Noida
Best M Tech Colleges in Delhi
Best M Tech Colleges in Gurgaon
Best M Tech Colleges in UP
Best M Tech Colleges in India
Best M Tech Colleges in Hyderabad
Best M Tech Colleges in Bangalore
Best M Tech Colleges in Chennai

At 2:36 AM, Blogger preeti verma said...

Best MCA colleges in greater noida
Best MSC IT colleges in greater


Best M TECH colleges in greater


At 2:23 AM, Blogger Harminder Singh said...

Indian Cyber Army is now coming up with Ethical hacking training & Cyber Crime Investigation

At 1:32 AM, Blogger Harminder Singh said...

Indian Cyber Army is now coming up with Ethical hacking training & Cyber Crime Investigation.

At 6:13 AM, Blogger Arushi Chaya said...

I have really happy to these reading your post. This product control and maintenance of our health.The daily routine can assist you weight lose quickly and safely.My life is completely reworked once I followed this diet.I feeling nice concerning myself.

Herbalife in Chennai
Herbalife Nutrition Products
Nutrition centers in Chennai
Weight Loss in Chennai
Weight Gain in Chennai

At 12:53 AM, Blogger PRISCILLA SARA said...

Your site is amazing and your blogs are informative and knlowledgeble to my websites.This is one

of the best tips in my life. I have in quite some time.Nicely written and great info.Thanks to

share the more informations.

Deals in OMR
Offers in OMR
Offers in Chennai
Apartments in OMR
Car Wash in OMR
Automobiles in OMR
Used Cars in OMR
Car Accessories in OMR

At 4:53 AM, Blogger Akash Thakur said...

ielts coaching in gurgaon

At 4:09 AM, Blogger Anbarasan14 said...

Nice blog!! I really got to know many new tips by reading your blog. Thank you so much for a detailed information! It is very helpful to me. Kindly continue the work.

TOEFL Class in Chennai Porur
TOEFL Training in Iyyappanthangal
TOEFL Training in DLF
TOEFL classes in St.Thomas Mount
TOEFL Coaching in Ramapuram
TOEFL Classes in Mugalivakkam
TOEFL Training in Kolapakkam

At 1:49 AM, Blogger yuva rani said...

Excellent Blog!!! Such an interesting blog with clear vision, this will definitely help for beginner to make them update.
Data Science Training in Bangalore
Devops Institute in Bangalore
Devops Course in Bangalore


Post a Comment

<< Home