ceil()で独自に実装したいC。ソースコードのライブラリを検索してここで見つけましたが、理解するのはかなり難しいようです。きれいでエレガントなコードが欲しい。
私もSOで検索し、ここでいくつかの答えを見つけました。答えはどれも正しくないようです。答えの1つは次のとおりです。
#define CEILING_POS(X) ((X-(int)(X)) > 0 ? (int)(X+1) : (int)(X))
#define CEILING_NEG(X) ((X-(int)(X)) < 0 ? (int)(X-1) : (int)(X))
#define CEILING(X) ( ((X) > 0) ? CEILING_POS(X) : CEILING_NEG(X) )
私の知る限り、の戻り値の型はceil()int ではありません。ここでマクロはタイプセーフになりますか? さらに、上記の実装は負の数でも機能しますか?
それを実装する最良の方法は何ですか？
きれいなコードを提供できますか？
引用したマクロは、より大きな数値に対しては正しく機能しませんが、INT_MAX正確に double として表すことはできます。
正しく実装する唯一の方法ceil()(同等のアセンブリ命令を使用して実装できない場合) は、s_ceil.c最初のリンクの背後にあるソース ファイルで行われているように、浮動小数点数のバイナリ表現でビット操作を行うことです。コードがどのように機能するかを理解するには、基礎となるプラットフォームの浮動小数点表現を理解する必要があります (表現はおそらくIEEE 754になるでしょう) 。しかし、これを回避する方法はありません。
編集：
複雑さの一部は、s_ceil.c処理する特殊なケース (NaN、無限大) と、64 ビットの整数型が存在することを前提とせずに作業を行う必要があるという事実に起因しています。
すべてのビット操作の基本的な考え方は、仮数の小数ビットをマスクし、数値が 0 より大きい場合はそれに 1 を追加することです。すべてにおいて正しいこと。
ceil()これは、私が一緒に石畳にした for floatsの実例となるバージョンです。注意: これは特殊なケースを正しく処理せず、広範囲にテストされていないため、実際には使用しないでください。ただし、ビットいじりに含まれる原則を説明するのには役立ちます。ルーチンについて詳しくコメントしようとしましたが、IEEE 754 形式で浮動小数点数がどのように表現されるかを理解していることを前提としています。
union float_int
{
float f;
int i;
};
float myceil(float x)
{
float_int val;
val.f=x;
// Extract sign, exponent and mantissa
// Bias is removed from exponent
int sign=val.i >> 31;
int exponent=((val.i & 0x7fffffff) >> 23) - 127;
int mantissa=val.i & 0x7fffff;
// Is the exponent less than zero?
if(exponent<0)
{
// In this case, x is in the open interval (-1, 1)
if(x<=0.0f)
return 0.0f;
else
return 1.0f;
}
else
{
// Construct a bit mask that will mask off the
// fractional part of the mantissa
int mask=0x7fffff >> exponent;
// Is x already an integer (i.e. are all the
// fractional bits zero?)
if((mantissa & mask) == 0)
return x;
else
{
// If x is positive, we need to add 1 to it
// before clearing the fractional bits
if(!sign)
{
mantissa+=1 << (23-exponent);
// Did the mantissa overflow?
if(mantissa & 0x800000)
{
// The mantissa can only overflow if all the
// integer bits were previously 1 -- so we can
// just clear out the mantissa and increment
// the exponent
mantissa=0;
exponent++;
}
}
// Clear the fractional bits
mantissa&=~mask;
}
}
// Put sign, exponent and mantissa together again
val.i=(sign << 31) | ((exponent+127) << 23) | mantissa;
return val.f;
}
標準ライブラリの実装を使用することほど洗練されたものはありません。エレガントなコードほど常にエレガントなコードはありません。
それはさておき、このアプローチには 2 つの大きな欠点があります。
Xが より大きいINT_MAX + 1か小さい場合、INT_MIN - 1マクロの動作は未定義です。これは、実装によって、すべての浮動小数点数のほぼ半分に対して誤った結果が得られる可能性があることを意味します。また、IEEE-754 とは異なり、無効フラグも発生します。次のように、試したのと同様の方法で実装できますceil(この実装では、IEEE-754 の倍精度を想定しています)。
#include <math.h>
double ceil(double x) {
// All floating-point numbers larger than 2^52 are exact integers, so we
// simply return x for those inputs. We also handle ceil(nan) = nan here.
if (isnan(x) || fabs(x) >= 0x1.0p52) return x;
// Now we know that |x| < 2^52, and therefore we can use conversion to
// long long to force truncation of x without risking undefined behavior.
const double truncation = (long long)x;
// If the truncation of x is smaller than x, then it is one less than the
// desired result. If it is greater than or equal to x, it is the result.
// Adding one cannot produce a rounding error because `truncation` is an
// integer smaller than 2^52.
const double ceiling = truncation + (truncation < x);
// Finally, we need to patch up one more thing; the standard specifies that
// ceil(-small) be -0.0, whereas we will have 0.0 right now. To handle this
// correctly, we apply the sign of x to the result.
return copysign(ceiling, x);
}
そのようなものは、あなたが得ることができるのと同じくらいエレガントであり、それでも正しいです.
私は、Martin が彼の回答に入れた (一般的には良い!) 実装に関する多くの懸念にフラグを立てました。彼のアプローチを実装する方法は次のとおりです。
#include <stdint.h>
#include <string.h>
static inline uint64_t toRep(double x) {
uint64_t r;
memcpy(&r, &x, sizeof x);
return r;
}
static inline double fromRep(uint64_t r) {
double x;
memcpy(&x, &r, sizeof x);
return x;
}
double ceil(double x) {
const uint64_t signbitMask = UINT64_C(0x8000000000000000);
const uint64_t significandMask = UINT64_C(0x000fffffffffffff);
const uint64_t xrep = toRep(x);
const uint64_t xabs = xrep & signbitMask;
// If |x| is larger than 2^52 or x is NaN, the result is just x.
if (xabs >= toRep(0x1.0p52)) return x;
if (xabs < toRep(1.0)) {
// If x is in (1.0, 0.0], the result is copysign(0.0, x).
// We can generate this value by clearing everything except the signbit.
if (x <= 0.0) return fromRep(xrep & signbitMask);
// Otherwise x is in (0.0, 1.0), and the result is 1.0.
else return 1.0;
}
// Now we know that the exponent of x is strictly in the range [0, 51],
// which means that x contains both integral and fractional bits. We
// generate a mask covering the fractional bits.
const int exponent = xabs >> 52;
const uint64_t fractionalBits = significandMask >> exponent;
// If x is negative, we want to truncate, so we simply mask off the
// fractional bits.
if (xrep & signbitMask) return fromRep(xrep & ~fractionalBits);
// x is positive; to force rounding to go away from zero, we first *add*
// the fractionalBits to x, then truncate the result. The add may
// overflow the significand into the exponent, but this produces the
// desired result (zero significand, incremented exponent), so we just
// let it happen.
return fromRep(xrep + fractionalBits & ~fractionalBits);
}
このアプローチについて注意すべきことの 1 つは、非整数入力に対して不正確な浮動小数点フラグが発生しないことです。それはあなたの使用法にとって問題になるかもしれませんし、そうでないかもしれません。私がリストした最初の実装はフラグを立てます。
マクロ関数は良い解決策ではないと思います。マクロ関数は型安全ではなく、引数の複数評価 (副作用) があります。きれいでエレガントなfunctionを書くべきです。
回答にもっとジョークが含まれると予想していたので、いくつか試してみます
#define CEILING(X) ceil(X)
おまけ: 副作用の少ない
マクロ
#define CEILING(X) (-floor(-(X)))
負のゼロを気にする場合は、
#define CEILING(X) (NEGATIVE_ZERO - floor(-(X)))
NEGATIVE_ZERO の移植可能な定義は演習として残されています....おまけに、FP フラグも設定されます (OVERFLOW INVALID INEXACT)