《その122》符号無し整数の全ビットを回転させる　&　p.55演習2-2: C++，C++/CX に挑戦！

2017年11月13日

《その122》符号無し整数の全ビットを回転させる　&　p.55演習2-2

　符号無し整数の全ビットを右に回転させる場合について考えてみます。

　符号無し整数の全ビットを右に 1桁だけ回転させる場合、
　① 元の数の最下位ビットが 1であれば、回転後の最上位ビットは 1
　② 元の数の最下位ビットが 0であれば、回転後の最上位ビットは 0
になります。

【 ①の場合】


　①の例として、
    00000000000000000000000000000111 … (ⅰ)
の場合について考えてみます。

　(ⅰ)を右に 1ビットだけ回転さると、最下位ビットが最上位にまわって
    10000000000000000000000000000011 … (ⅱ)
になりますが、この(ⅱ)を作る方法を考えるわけです。


　(ⅰ)を右に 1ビットだけシフトさせるのは、
>>演算子を使えば（あるいは 2で割れば）可能です。そうすると
    00000000000000000000000000000011 … (ⅲ)
になります。

　次に、最上位ビットを 1 にしなければなりません。

(ⅲ)に
    10000000000000000000000000000000 … (ⅳ)
を加えれば、(ⅱ)を作ることができます。


    00000000000000000000000000000011 … (ⅲ)
 +) 10000000000000000000000000000000 … (ⅳ)
-------------------------------------
    10000000000000000000000000000011 … (ⅱ)


というわけで、
    10000000000000000000000000000000 … (ⅳ)
を作ることを考えてみます。

    00000000000000000000000000000000
の全ビットを ~演算子を使って反転させれば
    11111111111111111111111111111111
ができます。

　次に、これを右に 1ビットだけシフトさせると
    01111111111111111111111111111111
になるので、~演算子で反転させれば（あるいは 1Uを加えれば）
    10000000000000000000000000000000 … (ⅳ)
になります。

【 ②の場合】

②のときは、右に 1ビットだけシフトさせれば、1ビットの右回転と同じ結果になります。

新版明解C++中級編　p.55 演習2-2
　符号無し整数 x の全ビットを右に n ビット回転した値を返す関数 rrotate と、左に n ビット回転した値を返す関数 lrotate を作成せよ。
　　　unsigned rrotate(unsigned x, int n);
　　　unsigned lrotate(unsigned x, int n);
※ 回転とは、最下位ビットと最上位ビットがつながっているとみなしてシフトすることである。
　たとえば右に 5ビット回転した場合は、シフトによって弾き出されることになる下位 5ビットを上位にもってこなければならない。


// p55_演習2-2
#include <iostream>
using namespace std;

int count_bits(unsigned x) {
    int bits = 0;
    while (x) {
        if (x & 1U) bits++;
        x >>= 1;
    }
    return bits;
}

int int_bits() {
    return count_bits(~0U);
}

void print_bits(unsigned x) {
    for (int i = int_bits() - 1; i >= 0; i--)
        cout << ((x >> i) & 1U ? '1' : '0');
}

unsigned rrotate(unsigned x, int n) {
    while (n--) {
        unsigned q = x & 1U;
        //  xの最下位ﾋﾞｯﾄ1のとき … q = 1
        //  xの最下位ﾋﾞｯﾄ0のとき … q = 0
        unsigned top = (~0U / 2 + 1) * q;
        //  ~0U              : ( 11111111111111111111111111111111 )
        //  ~0U / 2          : ( 01111111111111111111111111111111 )
        //  ~0U / 2 + 1      : ( 10000000000000000000000000000000 )
        //  以上より
        //  q = 1 のとき top : ( 10000000000000000000000000000000 )
        //  q = 0 のとき top : ( 00000000000000000000000000000000 )
        x = top + x / 2;
        //  x / 2 … xの全ﾋﾞｯﾄを1ﾋﾞｯﾄ右にｼﾌﾄ｡最上位ﾋﾞｯﾄは0になる。
    }
    return x;
}

unsigned lrotate(unsigned x, int n) {
    return rrotate(x, int_bits() - n);
    // 回転の場合､｢左にnﾋﾞｯﾄｼﾌﾄ｣ は ｢右に(int_bits() - n)ﾋﾞｯﾄｼﾌﾄ｣と同じ。
}

int main() {
    unsigned u0, u1;
    int r_l, shift;

    while (1) {
        cout << "非負の整数(999で終了) : "; cin >> u0; u1 = u0;
        if (u0 == 999) break;
        cout << "右回転(1を入力) or 左回転(2を入力) : "; cin >> r_l;
        if (r_l != 1 && r_l != 2) break;
        cout << "シフト数 : "; cin >> shift;

        if (r_l == 1) {
            u1 = rrotate(u0, shift);
        }
        if (r_l == 2) {
            u1 = lrotate(u0, shift);
        }

        cout << "u0:入力値，u1:回転後\n";
        cout << "u0 = "; print_bits(u0);
        cout << "  ( 10進数の " << u0 << " )\n";
        cout << "u1 = "; print_bits(u1);
        cout << "  ( 10進数の " << u1 << " )\n\n";
    }
}