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

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

ただいまの
回答率

88.77%

整数のオーバーフローを防ぐには

解決済

回答 4

投稿 編集

  • 評価
  • クリップ 2
  • VIEW 2,029

yumetodo

score 4784

2数 MINMAX (MIN < MAX)が与えられた時に
a(MIN) = MINa(MAX) = MAXとなる数列

a(i) = ..., MAX - 2, MAX - 1, MAX, MIN, MIN + 1, MIN + 2, ..., MAX - 2, MAX - 1, MAX, MIN, MIN + 1, MIN + 2, ...

があり、MINMAXiが与えられた時のa(i)を求める一般式を求めたいと思って、Yahoo! 知恵袋にて質問をしました。
http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q14160801594

また、Twitterでも

のようにアドバイスを貰い

#include <type_traits>
template<bool con, typename T> using enable_if_t = typename std::enable_if<con, T>::type;
template<typename T, enable_if_t<std::is_integral<T>::value && std::is_signed<T>::value, std::nullptr_t> = nullptr>
constexpr T a(T min, T max, T n){
    return ((n - min) % (max - min + 1) + max - min + 1) % (max - min + 1) + min;
}
template<typename T, enable_if_t<std::is_unsigned<T>::value, std::nullptr_t> = nullptr>
constexpr T a(T min, T max, T n){
    return (n < min) 
        ? a(min, max, n + (max - min + 1) * ((min - n) / (max - min + 1) + 1)) 
        : (n - min) % (max - min + 1) + min;
}

という関数を作成しました。

http://melpon.org/wandbox/permlink/X9bbE8Bch292u68D

ところがTがsignedな整数の時(つまり上の方の関数が呼ばれた時)、MINMAXが極端に離れていると(INT_MININT_MAXとか)オーバーフローするように思います。

http://melpon.org/wandbox/permlink/6peDrRHeyrdQVjBo

これをどうにかしたいのですがコードが浮かびません。

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

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

質問への追記・修正、ベストアンサー選択の依頼

  • yumetodo

    2016/06/24 12:50

    min-maxを繰り返す数列を移動したものですね。

    キャンセル

  • 退会済みユーザー

    退会済みユーザー

    2016/06/24 12:51

    解決の一助になるようにと思っていましたが、こちらが頭が足らんばかりに、いらんこと言いました。大変失礼致しました。 単に計算式について、オーバーフローにならないためには ということですね。

    キャンセル

  • yumetodo

    2016/06/24 12:59

    いえいえ、質問を見ていただいただけでもありがたいです。

    キャンセル

回答 4

checkベストアンサー

0

こんにちは。

下駄を履かせて符号なし型へ変換して処理すれば大丈夫と思います。
一旦C++14で作ってC++11へ置き換えました。C++11のconstexprでは鬼のように見にくいです。

#include <iostream>
#include <type_traits>
#include <limits>

template<bool con, typename T> using enable_if_t = typename std::enable_if<con, T>::type;

template<typename T, enable_if_t<std::is_unsigned<T>::value, std::nullptr_t> = nullptr>
constexpr T a(T min, T max, T n)
{
    return (n < min) 
        ? a(min, max, n + (max - min + 1) * ((min - n) / (max - min + 1) + 1)) 
        : (n - min) % (max - min + 1) + min;
}

template<typename T, enable_if_t<std::is_integral<T>::value && std::is_signed<T>::value, std::nullptr_t> = nullptr>
constexpr T a(T min, T max, T n)
{
#if 0   // original
    return ((n - min) % (max - min + 1) + max - min + 1) % (max - min + 1) + min;
#elif 0 // need c++14
    typedef typename std::make_unsigned<T>::type Unsigned;
    Unsigned    on   = static_cast<Unsigned>(std::numeric_limits<T>::max())+1+n;
    Unsigned    omin = static_cast<Unsigned>(std::numeric_limits<T>::max())+1+min;
    Unsigned    omax = static_cast<Unsigned>(std::numeric_limits<T>::max())+1+max;
    Unsigned    omod = (omax - omin + 1);
    return (omod == 0)?n:(a(omin, omax, on)-(std::numeric_limits<T>::max()+1));
#else   // need c++11
    typedef typename std::make_unsigned<T>::type Unsigned;
    return ((min == std::numeric_limits<T>::min())
         && (max == std::numeric_limits<T>::max()))
        ? n
        : (a(
                static_cast<Unsigned>(std::numeric_limits<T>::max())+1+min,
                static_cast<Unsigned>(std::numeric_limits<T>::max())+1+max,
                static_cast<Unsigned>(std::numeric_limits<T>::max())+1+n
            )-(std::numeric_limits<T>::max()+1));
#endif
}

int main()
{
    std::cout << a(-100,  100, 12) << "\n";
    std::cout << a( 100,  200, 12) << "\n";
    std::cout << a(-200, -100, -99) << "\n";
    std::cout << a(-200, -100, 12) << "\n";
    std::cout << a(std::numeric_limits<int>::min(), 1000, 12) << "\n";
    std::cout << a(std::numeric_limits<int>::min(), std::numeric_limits<int>::max(), 12) << "\n";

    return 0;
}

【追加】
書き忘れてました。下駄を履かせればOKと思う根拠は下記です。

少し詳しい型変換の説明をみてます。「JIS X 3010 プログラム言語C」を参照していると書かれているので、規格的に大丈夫と期待。

符号なし整数と符号付き整数の演算は定義されてます。
unsined と intの演算は、intがunsignedへ変換されます。intをunsigendへ変換する時、intが負ならunsignedの最大値+1を加えて、intが2の補数表現でなくても2の補数表現の時と同じ結果になるよう定義されているようです。


【更に追加】
returnの計算に処理系依存が入ってましたので修正しました。
ついでにマクロを使ってC++11でも多少みやすくしました。(本音:C++14までメンテするのは面倒)

#include <iostream>
#include <type_traits>
#include <limits>
#include <typeinfo>

template<typename T>
constexpr typename std::make_signed<T>::type removeExcess(T value)
{
    typedef typename std::make_signed<T>::type Signed;
    #define LIMIT (static_cast<T>(std::numeric_limits<Signed>::max())+1)
    return (LIMIT < value)?(value-LIMIT):(static_cast<Signed>(value)-std::numeric_limits<Signed>::max()-1);
}

template<bool con, typename T> using enable_if_t = typename std::enable_if<con, T>::type;

template<typename T, enable_if_t<std::is_unsigned<T>::value, std::nullptr_t> = nullptr>
constexpr T a(T min, T max, T n)
{
    return (n < min) 
        ? a(min, max, n + (max - min + 1) * ((min - n) / (max - min + 1) + 1)) 
        : (n - min) % (max - min + 1) + min;
}

template<typename T, enable_if_t<std::is_integral<T>::value && std::is_signed<T>::value, std::nullptr_t> = nullptr>
constexpr T a(T min, T max, T n)
{
#if 0   // original
    return ((n - min) % (max - min + 1) + max - min + 1) % (max - min + 1) + min;
#else
    typedef typename std::make_unsigned<T>::type Unsigned;
    #define N       (static_cast<Unsigned>(std::numeric_limits<T>::max())+1+n)
    #define MIN     (static_cast<Unsigned>(std::numeric_limits<T>::max())+1+min)
    #define MAX     (static_cast<Unsigned>(std::numeric_limits<T>::max())+1+max)
    #define MOD     (MAX - MIN + 1)
    return (MOD == 0)?n:removeExcess(a(MIN, MAX, N));
#endif
}

int main()
{
    std::cout << a(-100,  100, 12) << "\n";
    std::cout << a( 100,  200, 12) << "\n";
    std::cout << a(-200, -100, -99) << "\n";
    std::cout << a(-200, -100, 12) << "\n";
    std::cout << a(std::numeric_limits<int>::min(), 1000, 12) << "\n";
    std::cout << a(std::numeric_limits<int>::min(), std::numeric_limits<int>::max(), 12) << "\n";

    return 0;
}

投稿

編集

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2016/06/25 15:37

    「マクロを使ってC++11でも多少みやすくしました。」ってこういう時はimpl関数を作るか、使い終わったらundefしとかないと汚染ががが。
    しっかし2の補数表現恐るべし。
    ところで、「std::numeric_limits<T>::max()+1」分ずらしてなんで正しい答えが出るのかわかっていなかったりします。NとMAXは打ち消すから数学的にはいいとしてMINが・・・。

    キャンセル

  • 2016/06/25 16:40

    全部、下駄履きさせた数値同士の減算か大小比較なので、下駄履きの影響は全て打ち消されます。
    線形演算はオフセットを付けても、最後にオフセットを引けば同じ結果になるのですよ。剰余は線形演算ではないので注意は必要ですが、出来上がった式をみて確認する感じです。

    汚染の問題は単なる手抜きですので、良しなにやって下さい。

    キャンセル

  • 2016/06/25 22:03

    ああ、だからremoveExcessがあるのか。

    キャンセル

0

計算式が正しいかは確認していませんが % (max - min + 1)の部分でINT_MAX(2147483647)とINT_MIN(-2147483648)を引数に取ると分母が0になります。
maxとminがmax = - 1 * (min + 1)となる場合ゼロ除算になるコードですのでエラー処理をする必要があります

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2016/06/24 13:53

    なるほど、0除算の可能性も有りましたか・・・。

    キャンセル

0

0~XXXを繰り返すことにして、そいつに(MIN~MAXとなるような)ゲタを履かせた方が楽じゃなかろか。

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

0

こんな感じでどうでしょうか。見やすくするためにconstexprを外しましたが、適宜直してください。
符号ありなし共通です。

template<typename T, enable_if_t<std::is_integral<T>::value, std::nullptr_t> = nullptr>
//constexpr T a(T min, T max, T n)
T a(T min, T max, T n)
{
    std::make_unsigned<T>::type length = max - min + 1;
    return (n >= min) ? (n - min) % length + min
                      : (length - (min - n) % length) % length + min;
}

投稿

編集

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2016/06/24 20:31

    テストしたらバグってたので修正しました。

    キャンセル

  • 2016/06/24 21:58

    max - min+1のオーバーフローは符号付き演算のオーバーフローなので未定義動作にならないでしょうか?
    符号付き整数を2の補数表現している処理系なら期待通りに動作するケースが多いと思います。
    しかし、そもそも符号付き整数を2の補数表現していない処理系が存在するのか疑わしく感じますね。1Byte!=8Bitsな処理系のように都市伝説的にどこかに存在しているかも?

    あああ、そういえば私の回答に根拠を書き忘れてました。
    追加しておきます。

    キャンセル

  • 2016/06/24 23:19

    > 符号付き演算のオーバーフローなので未定義動作にならないでしょうか?

    確かにその通りですね。実用上は問題ない場合が多いとは思いますが、問題があるなら適宜修正ですね。

    キャンセル

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

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

関連した質問

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