論理シフト

id:bellbind:20060603:1149366839

で、問題の箇所は二分探索での中間位置を求めるコード

mid = (low + high) / 2;

がオーバーフローするのが問題で、解決方法として

• mid = low + (high - low) / 2;

や

• mid = (low + hight) >>> 1;

があがっている。前者は意味的には、低いほうと、そこから末端までの数(high - low)の半分を足したものである。むしろ自然な解である。

後者は、二つの正のintを足してもビット的には、符号に割り込むだけ（符号を超えてまであふれはしない）ので、論理右シフト(0埋め右シフト)を使うことで、1/2を実現している。

indexの最大が、INT_MAXの半分より1多い場合(0x40 00 00 00 (0x40 = 0100 0000))で、一番右に答えがある(0x40 00 00 00 + 0x 40 00 00 00)と、このオーバーフロー状態が起きる(0x 80 00 00 00 (0x80=1000 0000))。

ただし、INT_MAX(0x7f ff ff ff (0x7f = 0111 1111))であっても二つ足しても、オーバーフローはせいぜい符号領域へ割り込むだけ(0xff ff ff fe (0xfe = 1111 1110))なので、0埋め右シフトで1つ動かせば、正しく1/2にすることができるということになる。この方法が使えるのは、正の数同士を二つ足して1/2する場合だからであり、(a + b + c + d) / 4とかはたぶん無理だろう。(((a + b) / 2 + c) / 2) + d) / 2 はいいかも。