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

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

新規登録して質問してみよう
ただいま回答率
85.50%
C++11

C++11は2011年に容認されたC++のISO標準です。以前のC++03に代わるもので、中枢の言語の変更・修正、標準ライブラリの拡張・改善を加えたものです。

Q&A

解決済

4回答

2995閲覧

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

yumetodo

総合スコア5850

C++11

C++11は2011年に容認されたC++のISO標準です。以前のC++03に代わるもので、中枢の言語の変更・修正、標準ライブラリの拡張・改善を加えたものです。

1グッド

2クリップ

投稿2016/06/23 17:00

編集2016/06/24 03:10

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

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

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

また、Twitterでも

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

cpp

1#include <type_traits> 2template<bool con, typename T> using enable_if_t = typename std::enable_if<con, T>::type; 3template<typename T, enable_if_t<std::is_integral<T>::value && std::is_signed<T>::value, std::nullptr_t> = nullptr> 4constexpr T a(T min, T max, T n){ 5 return ((n - min) % (max - min + 1) + max - min + 1) % (max - min + 1) + min; 6} 7template<typename T, enable_if_t<std::is_unsigned<T>::value, std::nullptr_t> = nullptr> 8constexpr T a(T min, T max, T n){ 9 return (n < min) 10 ? a(min, max, n + (max - min + 1) * ((min - n) / (max - min + 1) + 1)) 11 : (n - min) % (max - min + 1) + min; 12}

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

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

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

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

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

maisumakun👍を押しています

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

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

退会済みユーザー

退会済みユーザー

2016/06/24 00:24

計算機上での計算の問題でしょうから、回答ではないのですが、 min maxがいくつだろうと a(i) = i ですよね。 もともとの (i-min)%(max-min+1)+min は iなのは 証明できそうな気がするのですが。
yumetodo

2016/06/24 03:03

>a(i) = i ですよね 違います。
退会済みユーザー

退会済みユーザー

2016/06/24 03:48 編集

定義だけみてました。 いろいろ数字いれて、たぶんそういう値が求めたいものなんだろうなということはなんとなくわかりましたが、上の定義からはそれが正しいのかはわからないのですよ。 min-maxを繰り返す数列を移動したもの で合っていますでしょうか?
yumetodo

2016/06/24 03:48

リンクを張っている知恵袋の方には、「たとえばMIN =-1, MAX = 4のとき a(i) = ..., 3, 4, -1, 0, 1, 2, 3, 4, -1, 0, ... となります(a(0)=0, a(1)=1,...)。」と書いていたんですが、質問の筋から外れるので除去してました
yumetodo

2016/06/24 03:50

min-maxを繰り返す数列を移動したものですね。
退会済みユーザー

退会済みユーザー

2016/06/24 03:51

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

2016/06/24 03:59

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

回答4

0

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

C++

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

投稿2016/06/24 11:14

編集2016/06/24 11:36
catsforepaw

総合スコア5938

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

catsforepaw

2016/06/24 11:31

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

2016/06/24 12:58

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

2016/06/24 14:19

> 符号付き演算のオーバーフローなので未定義動作にならないでしょうか? 確かにその通りですね。実用上は問題ない場合が多いとは思いますが、問題があるなら適宜修正ですね。
guest

0

ベストアンサー

こんにちは。

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

C++

1#include <iostream> 2#include <type_traits> 3#include <limits> 4 5template<bool con, typename T> using enable_if_t = typename std::enable_if<con, T>::type; 6 7template<typename T, enable_if_t<std::is_unsigned<T>::value, std::nullptr_t> = nullptr> 8constexpr T a(T min, T max, T n) 9{ 10 return (n < min) 11 ? a(min, max, n + (max - min + 1) * ((min - n) / (max - min + 1) + 1)) 12 : (n - min) % (max - min + 1) + min; 13} 14 15template<typename T, enable_if_t<std::is_integral<T>::value && std::is_signed<T>::value, std::nullptr_t> = nullptr> 16constexpr T a(T min, T max, T n) 17{ 18#if 0 // original 19 return ((n - min) % (max - min + 1) + max - min + 1) % (max - min + 1) + min; 20#elif 0 // need c++14 21 typedef typename std::make_unsigned<T>::type Unsigned; 22 Unsigned on = static_cast<Unsigned>(std::numeric_limits<T>::max())+1+n; 23 Unsigned omin = static_cast<Unsigned>(std::numeric_limits<T>::max())+1+min; 24 Unsigned omax = static_cast<Unsigned>(std::numeric_limits<T>::max())+1+max; 25 Unsigned omod = (omax - omin + 1); 26 return (omod == 0)?n:(a(omin, omax, on)-(std::numeric_limits<T>::max()+1)); 27#else // need c++11 28 typedef typename std::make_unsigned<T>::type Unsigned; 29 return ((min == std::numeric_limits<T>::min()) 30 && (max == std::numeric_limits<T>::max())) 31 ? n 32 : (a( 33 static_cast<Unsigned>(std::numeric_limits<T>::max())+1+min, 34 static_cast<Unsigned>(std::numeric_limits<T>::max())+1+max, 35 static_cast<Unsigned>(std::numeric_limits<T>::max())+1+n 36 )-(std::numeric_limits<T>::max()+1)); 37#endif 38} 39 40int main() 41{ 42 std::cout << a(-100, 100, 12) << "\n"; 43 std::cout << a( 100, 200, 12) << "\n"; 44 std::cout << a(-200, -100, -99) << "\n"; 45 std::cout << a(-200, -100, 12) << "\n"; 46 std::cout << a(std::numeric_limits<int>::min(), 1000, 12) << "\n"; 47 std::cout << a(std::numeric_limits<int>::min(), std::numeric_limits<int>::max(), 12) << "\n"; 48 49 return 0; 50}

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

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

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


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

C++

1#include <iostream> 2#include <type_traits> 3#include <limits> 4#include <typeinfo> 5 6template<typename T> 7constexpr typename std::make_signed<T>::type removeExcess(T value) 8{ 9 typedef typename std::make_signed<T>::type Signed; 10 #define LIMIT (static_cast<T>(std::numeric_limits<Signed>::max())+1) 11 return (LIMIT < value)?(value-LIMIT):(static_cast<Signed>(value)-std::numeric_limits<Signed>::max()-1); 12} 13 14template<bool con, typename T> using enable_if_t = typename std::enable_if<con, T>::type; 15 16template<typename T, enable_if_t<std::is_unsigned<T>::value, std::nullptr_t> = nullptr> 17constexpr T a(T min, T max, T n) 18{ 19 return (n < min) 20 ? a(min, max, n + (max - min + 1) * ((min - n) / (max - min + 1) + 1)) 21 : (n - min) % (max - min + 1) + min; 22} 23 24template<typename T, enable_if_t<std::is_integral<T>::value && std::is_signed<T>::value, std::nullptr_t> = nullptr> 25constexpr T a(T min, T max, T n) 26{ 27#if 0 // original 28 return ((n - min) % (max - min + 1) + max - min + 1) % (max - min + 1) + min; 29#else 30 typedef typename std::make_unsigned<T>::type Unsigned; 31 #define N (static_cast<Unsigned>(std::numeric_limits<T>::max())+1+n) 32 #define MIN (static_cast<Unsigned>(std::numeric_limits<T>::max())+1+min) 33 #define MAX (static_cast<Unsigned>(std::numeric_limits<T>::max())+1+max) 34 #define MOD (MAX - MIN + 1) 35 return (MOD == 0)?n:removeExcess(a(MIN, MAX, N)); 36#endif 37} 38 39int main() 40{ 41 std::cout << a(-100, 100, 12) << "\n"; 42 std::cout << a( 100, 200, 12) << "\n"; 43 std::cout << a(-200, -100, -99) << "\n"; 44 std::cout << a(-200, -100, 12) << "\n"; 45 std::cout << a(std::numeric_limits<int>::min(), 1000, 12) << "\n"; 46 std::cout << a(std::numeric_limits<int>::min(), std::numeric_limits<int>::max(), 12) << "\n"; 47 48 return 0; 49}

投稿2016/06/24 06:49

編集2016/06/25 00:44
Chironian

総合スコア23272

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

yumetodo

2016/06/24 15:21

ちょっとゆっくり考えながら見ますが、「std::numeric_limits<T>::max()+1」ってなんで大丈夫なんでしょう?
Chironian

2016/06/25 00:42 編集

あ、std::numeric_limits<T>::max()+1やっちゃいました。 大丈夫なのは2の補数表現だからだと思います。 -std::numeric_limits<T>::max()-1とすれば良いような気もしますが、ダメですね。 return文の最後の計算で、unsigned - unsignedしてますが、これもunsignedです。それを無理っとint型へ暗黙の型変換しているのでここも処理系依存してます。 う~~ん、これは困りました。 といいますか、符号なし整数同士の引き算の結果が負になると処理系依存コードになってしまうってことですね。これは。 MinGW 5.2.0でtypeid(decltype(10u-20u)).name()をデマングルするとunsigned intでした...あう。 符号無し整数の引き算が負になるようなコードってたくさん書いている気がします。 符号付き整数を2の補数表現していない処理系なんて存在しないと信じるしかないかも? 【追記】 一晩たって解を思いつきましたので、回答に追加します。 しかし、私のように符号付き整数同士の引き算が負になることが未定義と思っていなかった人は少なくない気がします。何か根本的なことを勘違いしているかも?
yumetodo

2016/06/25 06:37

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

2016/06/25 07:40

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

2016/06/25 13:03

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

0

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

投稿2016/06/24 05:56

episteme

総合スコア16614

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

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

投稿2016/06/24 04:52

stfl

総合スコア19

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

yumetodo

2016/06/24 04:53

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問