Wednesday, October 18, 2006

Math.abs Returns a Negative Number

Math.abs (Math.Abs in C# :-) is one of those methods that sould be pretty simple, right? Just take the value, if it's negative, return a positive version, duh! Well, it's not that simple.

There are 232 possible values of int, each of which is positive, negative or zero. There's only one integer that is zero, namely 0x00000000. That means that either there is one bit pattern of ints that doesn't represent an integer, or there is not a 1-1 mapping between positive and negative numbers. It turns out, the second is the case. The odd number is int.MinValue, which is equal to 0x80000000 in binary.

What happens when you negate this number? In two's complement -x=~x+1. ~x = 0x7fffffff. ~x+1=0x80000000. That means -int.MinValue == int.MinValue. Uh oh!

Enter Math.abs. What's the function to do when passed int.MinValue. Well, in C#, Math.Abs throws an OverflowException. Java, on the other hand, happily returns int.MinValue. Either way, the caller of the function probably wasn't expecting this.

I discovered this oddity when reading Effective Java (kindly provided to all Google Engineers). The book talks about the code: Math.abs (new Random ().nextInt ()) % n as a way to generate random numbers between 0 and n. This code usually works, except when Random happens to return int.MinValue. In this case, the abs returns a negative value, causing the modulus operator to return a negative number. Eeeek!

At this point, I realized that for the data structures course I TA, many students used a similar piece of code in a hashtable they wrote. I wrote a quick script to check how many people screwed up on int.MinValue. Most students did.

I wondered how much this occurred in production code. Luckily, I had one of the best test cases at my fingertips. Google has an internal "grep" tool (the inspiration for the new Code Search) utility. I made a quick regex to find where this occurred. There were many instances.

Now that Google has released an external version of this tool, you can see some of the places this anti-pattern is used in the real world:

Each of these snippits is a time bomb. One in 232 executions, the function will do something strange.

Having found this issue in Google's source code, I emailed somebody inside Google who had been running FindBugs internally. He in turn talked to Bill Pugh, who added a detector. I added a test case to the test suite for the homework assignment at CMU, so students will have to handle this case. All in all, a very obscure bug

So, what should you do rather than Math.abs? I've seen primarially two buggy patterns:

  • Hashtables People want to find "which bucket should I put an object with hashcode x in". The best way to do this is (o.GetHashCode () & 0x7fffffff) % table.Length. This has the advantage of being faster than Math.abs (no branches).
  • Random Numbers People want to say Math.Abs (new Random ().Next ()) % N. Not only is this buggy in the rare case, it can also cause a bad distribution of numbers for large N. Use the Next (int, int) method which allows you to specify bounds

11 comments:

Anonymous said...

Awesome. I wonder what other langs/libs do.

Anonymous said...

Why didn't people just remember that the range for n-bit signed integers is really -2^(n-1) to 2^(n-1)-1?

erik said...

To sun's credit, they have documented this anomaly in the documentation for Math.abs():


if the argument is equal to the value of Integer.MIN_VALUE, the most negative representable int value, the result is that same value, which is negative.


I still wouldn't expect a negative number though :-)

Viraptor said...

Libc does the same for INT_MIN. So most c/c++ projects do the same, but you shouldn't really expect any abs(rand()) code there.
It will happen less often, but still - I don't know of anyone who thought of this up to now.
Now... they're panicing ;)

Axel Liljencrantz said...

'abs(rand())%n' is broken, just as you say. However 'abs(rand()%n)' isn't, and the bit about the lower bits of output from random number generators being less random than the high bits are bogus on all modern systems. rand() implementations old enough to have such issues are so fundamentally broken that trying to 'fix' things by using high order bits won't really help either.

RichB said...

What happens on a 64bit CLR, or 64bit JVM? Do 32bit CPU instructions get used, or do 64bit instructions get used and the result truncated like with Java/strictfp?

Ben Maurer said...

'abs(rand()%n)' is still broken. Let's say n is MaxInt*2/3. Then 2/3rds of random numbers will be < 1/3, and 1/3rd will be > 1/3. Clearly broken

Anonymous said...

public static int abs(int a) {
return (a < 0) ? -a : a;
}

(0 - Integer.MIN_VALUE) equals Integer.MIN_VALUE

The anomaly here is that in stead of throwing an exception, the JVM lets positive numbers overflow into negative and vice-verca. But everybody knows that :-)

mauhiz said...

a solution could be to have Math.abs(int) return a long

Tim said...

Good Job! :)

潇洒光头、 said...

●●百度类●●:
代孕 淘宝刷信用
北京发票 代开发票
餐饮发票 住宿发票
广告发票 对讲机
传世私服 传奇世界私服
新开传世私服 传奇私服
天龙八部私服 天龙私服
苏州办证
手机窃听器 手机窃听器
手机窃听器
手机监听器
手机监听器
手机窃听器
代写论文 代写论文
北京办证 办证
代孕 代孕网
代孕 代孕
代孕 试管婴儿
代写论文 代写论文
代写代发 论文代写 dhl

●●Google类●●:
modern abstract art sofa manufacturer
净水器 开水器 净水机 净水 软水机 软水 直饮机 家用净水 家用净水器 家用净水机 中央净水 中央净水器 水家装 水家电 水卫士 混合机
过滤机 DHL快递 俄罗斯签证
保险箱 法兰 法兰标准
polycarbonate sheet 回流焊 波峰焊
免烧砖机 注册上海公司 儿童摄影
牛皮癣 皮肤病 制氮机
食堂售餐机 校园一卡通
学校一卡通 ic卡售饭机
食堂售饭机 深圳一卡通
广东售饭机 机电设备安装
北京发票 代开发票
餐饮发票 住宿发票
广告发票
网络电话 免费网络电话
假发 补发
织发 植发
压滤机 板框压滤机
蒸馏水机 纯蒸气发生器
上海搬家公司 上海搬场公司
大众搬家 大众搬场
张家界旅游 香港旅游
深圳旅行社 打包机
收缩机 对讲机 电源模块
血管栓塞剂
售饭机 水控机 水控器
萎缩性胃炎 neoprene laptop bags
SEO优化
SEO优化 计量泵
胃炎 胃病
冷水机 冰水机
工业冷水机
北京特价机票 北京打折计票 北京国际机票
北京机票预定 北京飞机票
北京订机票 北京机票查询 饮料机械
血糖仪 血糖仪
银杏 水培花卉 企业宣传片 空分设备
化工泵 离心机
电话交换机 程控交换机 集团电话 集装袋
混合机 混合机
混合机捏合机 捏合机
捏合机导热油炉 导热油炉
导热油炉 反应釜 反应釜
反应釜 spherical roller bearing
搬运车 搬运车 电动搬运车 油桶搬运车 堆高车 电动堆高车 半电动堆高车 堆垛车
高空作业平台车 电动叉车 平衡重叉车 前移叉车 电瓶叉车
韩国饰品批发 模块电源
X架 超薄灯箱> 易拉宝 展柜制作
代理服务器 游戏加速器 网络加速器
网通加速器 电信加速器 电信网通转换器
电信网通加速器 网通电信互转
网通电信互通 网络游戏加速器
美国VPN代理 美国独享VPN 美国独享IP
pvc ceiling panel Spherical roller bearings
SEO优化
安全鞋 劳保鞋 防砸鞋 电绝缘鞋 上海安全鞋 上海劳保鞋 江苏劳保鞋
服装软件 服装管理软件 进销存软件
进销存管理软件 服装管理系统 服装进销存软件
进销存系统 进销存管理系统 免费进销存软件
吉林中医 东北特产
打包机
阳痿 阴茎短小 阴茎增大
早泄 前列腺炎 阴茎增粗 阴茎延长
国际机票 上海国际机票
国际特价机票 国际打折机票
CRM 客户管理软件 客户关系管理
免费客户管理软件 客户管理软件下载 客户信息管理系统 销售管理系统 销售管理
CRM系统 CRM软件 客户关系管理系统
客户关系管理软件 客户管理 客户管理系统 营销管理系统 客户资源管理 销售管理软件 客户资料管理软件 客户资源管理软件
客户信息管理软件 客户资料管理 客户资源管理 客户信息管理 客户资料管理系统
客户资源管理系统 客户管理软件免费版
砂磨机 砂磨机
砂磨机 卧式砂磨机
卧式砂磨机 卧式砂磨机
三辊研磨机 三辊研磨机
三辊研磨机 混合机 混合机
混合机 锥形混合机 锥形混合机 锥形混合机 行星动力混合机 行星动力混合机 行星动力混合机 无重力混合机 无重力混合机 无重力混合机
干粉砂浆设备 干粉砂浆设备
干粉砂浆设备 捏合机 捏合机 捏合机 导热油炉 导热油炉 导热油炉 反应釜 反应釜 反应釜 搪玻璃反应釜 搪玻璃反应釜 搪玻璃反应釜
乳化机 涂料设备 干混砂浆设备 无重力混合机 胶体磨 涂料成套设备 双螺旋混合机
北京婚庆 北京婚庆公司
400电话
办证 呼吸机 制氧机
亚都 亚都加湿器 亚都净化器
亚都装修卫士
饰品批发 小饰品批发 韩国饰品 韩国饰品批发 premature ejaculation penis enlargement
破碎机 制砂机 球磨机 雷蒙磨 雷蒙磨粉机 鄂式破碎机 鄂式破碎机 免烧砖机 加气混凝土设备
反击式破碎机 选矿设备
安利产品 马来西亚留学
网站优化 网站推广
衬布
代写论文
代写论文
论文代写 代写论文
磁力泵
离心泵
化工泵
隔膜泵
螺杆泵
潜水泵
油泵
耐腐蚀泵
水泵
拖链 防护罩 排屑机 塑料拖链 钢铝拖链
化工离心泵
计量加油泵
自吸式离心泵
管道油泵
自吸式排污泵
潜水排污泵
自吸式磁力泵
耐高温磁力泵
不锈钢多级离心泵
多级离心泵
耐腐蚀自吸泵
自吸化工泵
玻璃钢液下泵
液下式排污泵
卧式离心清水泵
氟塑料磁力泵
磁力驱动循环泵
耐腐蚀污水泵
卧式化工离心泵
玻璃钢耐酸泵
防爆管道油泵
不锈钢多级泵
立式多级离心泵
塑料磁力泵
水泵厂
手摇油泵
上海水泵厂
上海水泵
离心泵厂家
热水泵
清水泵
气动隔膜泵
深圳装饰 深圳装饰公司 深圳装修公司
特价机票 打折机票 国际机票
机票
新风换气机 换气机 立式新风换气机 风机箱 新风系统 能量回收机
搅拌机 混合机 乳化机
分散机
毛刷 毛刷辊 工业毛刷 刷子 钢丝刷
涂层测厚仪 硬度计
兆欧表 激光测距仪
测振仪 转速表
温湿度计 风速仪
超声波测厚仪
粗糙度仪
噪音计 红外测温仪
万用表
硬度计 万用表
美容院 美容加盟
澳洲留学 澳大利亚留学
什么是法兰
电烤箱
酒店预定 北京酒店预定 北京酒店
离心机
nail equipment nail products nail product nail uv lamp nail uv lamp nail uv lamps uv nail lamp nail brush
nail file nail tool nail tip nail gel curing uv lamps lights
万用表 风速仪
红外测温仪 噪音计
苗木价格 苗木信息 标牌制作 深圳标牌 北京儿童摄影 防静电鞋 淘宝刷信誉
威海凤凰湖 威海海景房 大庆密封件
打标机 淘宝刷信誉 TESOL/TEFL国际英语教师证书 英语教师进修及培训 北京快递公司 北京国际快递