アルゴリズム・ネタ

知ってる／知らない系ってところですが、最近業務で必要になったもの、

1. 最小公倍数と最大公約数
2. ビット列を保持した整数変数内の立っている最上位ビット／最下位ビットを得る
3. ビット列を保持した整数変数内の立っているビットの数を数える
4. ユニークでない値を格納したソート済み配列から、特定の値が存在するインデックスの範囲を求める

どれも定石な気がするんだけど。

最小公倍数と最大公約数

公式のままってかんじ？

/// <summary>最大公約数 </summary>
int GCD(int n, int m)
{
    if (n > m) return GCD(m, n);
  
    while (n != 0)
    {
        int t = m % n;

        m = n;
        n = t;
    }

    return (m > 0) ? m : -m;
}

/// <summary>最小公倍数</summary>
int LCM(int n, int m)
{
    if ((n == 0) || (m == 0)) return 0;
    return n * m / GCD(n, m);
}

立っている最上位ビット／最下位ビットを得る

テキトウすぎ…、

// <summary>最も下位のビットを得る</summary>
int LeastBit(int value)
{
    if (value == -0x80000000) return value;
    return ((value ^ (value - 1)) + 1) >> 1;
}

// <summary>最も上位のビットを得る</summary>
int MostBit(int value)
{
    if (value == 0) return value;
    return 1 << Log2(value);
}

Log2() は底が 2 の対数を得る関数なんだけど、そっちが >> でループしてるのがテキトウな感じ。

立っているビットの数を数える

LeastBit の要領でビットの数だけループするとか、

/// <summary>起きているビットの数</summary>
int RaiseBits(int value)
{
    int count = 0;

    while (value != 0)
    {
        count++;
        value = value & (value - 1);
    }

    return count;
}

２進数表記を数式的にと見て、有効な項の数を計算するとか、
http://www.st.rim.or.jp/~phinloda/cqa/cqa15.html#Q2
http://www.st.rim.or.jp/~phinloda/cqa/cqa15.html#Q3
……フィンローダさんって裏とか表とか、いったい何個のブログを平行運用してるんだろう（笑