質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

89.69%

ビットの回転について

解決済

回答 4

投稿

  • 評価
  • クリップ 0
  • VIEW 3,862

kamecha

score 39

前提

現在書籍でc言語を学習している者です。
その書籍の演習問題は解答が存在しておらず(著者の意図的に)
学習を進めることが困難な時があるので、問題のヒント等を教えていただきたいです。

問題

符号なし整数xの全ビットを右にnビット回転した値を返す関数rrotateと、左にnビット回転した値を返す関数lrotateを作成せよ。

unsigned rrotate(unsigned x, int n){/* ...  */}
unsigned lrotate(unsigned x, int n){/* ...  */}


※回転とは、再開ビットと最上位ビットがつながっているとみなしてシフトすることである。

該当のソースコード

#define bitMax 2147483647 /*最上位ビット以外1*/

unsigned rrotate (unsigned x, int n){
    int i;
    for(i = 0; i < n; i++){
        if(x & 1U){
            x >>= 1;
            x ^ ~bitMax;
        }else{
            x >>= 1;
        }
    }
    return x;
}

疑問点

xの最下位ビットが1であれば全ビットを右に1シフトして、
最上位ビットのみ1である ~bitMaxと排他的論理和をすれば、良いのでは?
と、思ったのですが上手く動作しませんでした。

この方法では、この問題は解けないのかどうか知りたいです。

また、ネットで調べてみると右にシフトした後左にシフトし・・・
といった方法があるみたいですが、良く分からなかったのでその解説もしていただけると有り難いです。

補足情報

左回りは右回りの理解ができたらしようと思っています。

int型が32ビットの実行環境
書籍 新・明解 c言語 入門編
演習 7-3

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 4

+3

こんにちは。

x ^ ~bitMax;x=が漏れているだけでは?
ところで、排他的論理和でダメではないですが、このような時は論理和を使った方が素直と思います。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/08/27 08:32

    有り難うございます。
    簡単なミスがあったみたいです。

    キャンセル

+3

こんにちは。

また、ネットで調べてみると右にシフトした後左にシフトし・・・
といった方法があるみたいですが、良く分からなかったのでその解説もしていただけると有り難いです。

おそらく、次の画像のようなイメージかと思われます。
イメージ説明
n ビット右シフトした値と、32-n ビット左シフトした値の論理和をとれば、求めたい値になるはずです。

unsigned int rrotate (unsigned int x, unsigned int n) {
  return x>>n | x<<(32-n);
}

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/08/27 08:33

    有り難うございます。
    図を使った解説とても分かりやすかったです。

    キャンセル

+2

最下位ビットが1であればシフト後に最上位ビットを1にするというアプローチは方法の一つとして問題ないと思います。
この場合、シフト後に取得するのは排他的論理和ではなく、論理和ではないでしょうか。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/08/27 08:26

    なるほど!論理和の方がすっきりしてますね。

    キャンセル

checkベストアンサー

0

ちゃんと実装してみました。

#include <limits.h>

unsigned int rrotate(unsigned int x, int n);
unsigned int lrotate(unsigned int x, int n);

#define UINT_BIT (sizeof(unsigned int) * CHAR_BIT)

unsigned int rrotate(unsigned int x, int n)
{
    n %= UINT_BIT;
    if (n < 0) n += UINT_BIT;
    return (x >> n) | (x << (UINT_BIT - n));
}

unsigned int lrotate(unsigned int x, int n)
{
    return rrotate(x, -(n % UINT_BIT));
}

まず、UINT_BITunsigned intのビット数です。sizeofでバイト数を求めて1バイトのビット数であるCHAR_BITをかけています。

全ての肝は、(x >> n) | (x << (UINT_BIT - n))の部分です。x >> nxnビット右にずらす事になりますが、左側のnビット分が全て0になってしまいます。ここにちょうど、もともとのxでの右側nビット分が入れば良い事になります。xは全体でUINT_BITありますからUINT_BIT - nビット分左にずらせば、ちょうど良く、右側nビット分が先頭に来ることになり、残りは0になります。それがx << (UINT_BIT - n)の部分です。あとは、この二つのビット和を取れば、回転したものになります。なお、負の値は逆方向とも考えられます。つまり、左回転は右回転での負の方向と言うだけです。

nUINT_BITを超える場合や負の場合は、UINT_BIT毎回転した場合は同じであるという性質から、適切なUINT_BITの倍数を加算または減算すれば良い事になります。つまりそれはUINT_BITで割った余りを求めるのと同じです。

さて、これで済んでいれば簡単ですが、C言語特有の動作未定義や実装依存を考慮しなければなりません。

  • シフト演算子右辺値が負の値またはビット数を超える場合は動作未定義。
  • INT_MIN-単項演算子はオーバーフローするため動作未定義。
  • %の商が切り詰められる方向は、C99より前は実装依存、C99以降は0の方向。

そういった諸々を考慮した結果、上のコードになります。


【おまけ】
1ビットずつずらす版も作りました。nが大きいととても遅いです。最適化しない場合や、最適化が甘いコンパイラでコンパイルした場合、スタックオーバフローを起こす場合があります。(GCCで-O2なら大丈夫です)

#include <limits.h>

unsigned int rrotate(unsigned int x, int n);
unsigned int lrotate(unsigned int x, int n);

#define UINT_BIT (sizeof(unsigned int) * CHAR_BIT)
#define UINT_TOP_BIT (0x1u << (UINT_BIT - 1))

unsigned int rrotate(unsigned int x, int n)
{
    if (n == 0)
        return x;
    else if (n < 0)
        return rrotate((x << 1) | (!!(UINT_TOP_BIT & x)), n + 1);
    else
        return rrotate((x >> 1) | (UINT_TOP_BIT * (x & 0x1u)), n - 1);
}

unsigned int lrotate(unsigned int x, int n)
{
    if (n < -INT_MAX)
        return rrotate((x >> 1) | (UINT_TOP_BIT * (x & 0x1u)), -(n + 1));
    return rrotate(x, -n);
}

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/08/27 21:57

    なるほど。
    度々すみませんが、(UINT_TOP_BIT * (x & 0x1u))はどういう働きをしているのですか?
    特に*は、最上位ビットのみが1のビットと、入力値と最下位ビットのみが1のビットとの論理積をかける、ということですか?

    キャンセル

  • 2017/08/27 23:09

    本当は
    (x & 0x1u) ? UINT_TOP_BIT : 0
    と書こうとしたんですけど、0か1なら、そのままかけた方がはやくないかなとそうなってしまいました。
    !!(UINT_TOP_BIT & x)

    (UINT_TOP_BIT & x) ? 1 : 0
    と丁寧に書いた方が良かったような気がします。

    キャンセル

  • 2017/08/28 07:09

    条件式を使用すると、いうことなんですね!
    ありがとうございます。


    様々な方の解説をまとめた感じがして分かりやすかったです。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 89.69%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

同じタグがついた質問を見る