Skip to content

Instantly share code, notes, and snippets.

@tkihira
Last active August 29, 2015 14:10
Show Gist options
  • Save tkihira/adaa4d2b15b4cc6f1b9c to your computer and use it in GitHub Desktop.
Save tkihira/adaa4d2b15b4cc6f1b9c to your computer and use it in GitHub Desktop.
function max(a, b) {
// 差のある最上位のビットを立てる
// (例えば 11010010 と 10110101 の場合、 x は 01000000 )
var x = a ^ b;
x |= x >>> 1;
x |= x >>> 2;
x |= x >>> 4;
x |= x >>> 8;
x |= x >>> 16;
var h = x ^ (x >>> 1);
// ついでに、aとbが同値だった場合に使用するため、すべてのビットを埋める
x |= x << 1;
x |= x << 2;
x |= x << 4;
x |= x << 8;
x |= x << 16;
// a == b の場合はx == 0、それ以外の場合は x == 0xffffffff
// a の値と最上位差分ビットのマスクを取り、その結果を32bit全部埋める
var ma = (h & a);
ma |= ma >>> 1;
ma |= ma >>> 2;
ma |= ma >>> 4;
ma |= ma >>> 8;
ma |= ma >>> 16;
ma |= ma << 1;
ma |= ma << 2;
ma |= ma << 4;
ma |= ma << 8;
ma |= ma << 16;
// b の値と最上位差分ビットのマスクを取り、その結果を32bit全部埋める
var mb = (h & b);
mb |= mb >>> 1;
mb |= mb >>> 2;
mb |= mb >>> 4;
mb |= mb >>> 8;
mb |= mb >>> 16;
mb |= mb << 1;
mb |= mb << 2;
mb |= mb << 4;
mb |= mb << 8;
mb |= mb << 16;
// a と b それぞれにマスクをかけて max を導き出す
return ((a & ~x) | (a & ma) | (b & mb)) >>> 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment