c-最大整数函数(floor)可以用位运算符实现吗

Question

最大整数函数⌊x⌋是一个给出小于或等于给定实数x的最大整数的函数。它也被称为floor。

<math.h>标头提供floor，它计算不大于其浮点参数的最大整数值。

我想知道是否可以在像<<、>>或~这样的逐位运算符的帮助下实现这一点。

Answer 1

floor()对于常用的IEEE-754二进制浮点格式，并且可能对于所有二进制浮点格式都可以仅使用位运算来实现。由于这种方法的执行速度很慢，它可能几乎没有实际意义。

floor()使用四舍五入模式将浮点操作数向负无穷大舍入为整数。对于正操作数，floor()的行为与trunc()相同，后者也转换为整数，但使用舍入模式向零舍入。截断基本上是从浮点操作数中删除小数位数。

IEEE-754二进制浮点格式的二进制指数告诉我们浮点操作数的尾数(尾数(中分数位的起始位置，我们可以简单地屏蔽它们。非常大的数字不具有任何小数位数，并且大小小于1的数字仅具有小数位数，从而导致零。映射到float的IEEE-754binary32的truncf()的示例性实现如下：

float uint32_as_float (uint32_t a)
{
float r;
memcpy (&r, &a, sizeof r);
return r;
}
uint32_t float_as_uint32 (float a)
{
uint32_t r;
memcpy (&r, &a, sizeof r);
return r;
}
float my_truncf (float a) 
{ 
const uint32_t FP32_EXPO_MASK = 0x7f800000u;
const uint32_t FP32_ALL_ONES  = 0xffffffffu;
const uint32_t FP32_MAX_EXPO  = 128;
const uint32_t FP32_EXPO_BIAS = 127;
const uint32_t FP32_NBRBITS_M1= 31;
const uint32_t FP32_STORED_MANT_BITS = 23;
uint32_t s, t, ur, ua =  float_as_uint32 (a); 
s = ((ua & FP32_EXPO_MASK) >> FP32_STORED_MANT_BITS) - FP32_EXPO_BIAS; 
t = (s > FP32_STORED_MANT_BITS) ? 
((s > FP32_MAX_EXPO) ? FP32_NBRBITS_M1 : 0) : 
(FP32_STORED_MANT_BITS - s); 
ur = ua & (FP32_ALL_ONES << t); 
return uint32_as_float (ur);
}

对于负操作数，当操作数具有非零小数部分时，trunc()与floor()不同。因此，我们可以通过首先计算trunc()，然后有条件地从结果中减去1来构造floor()。显然，我们希望通过位级操作而不是浮点减法来实现这一点。我们观察到，如果浮点操作数足够大，减去1不会改变值。我们进一步观察到，如果负浮点操作数的幅度小于1但不为零，则在(-1，0(中，floor()的结果为-1。

对于我们确实需要减去1的情况，浮点操作数的指数告诉我们最低有效整数位位于有效位(尾数(内的位置。从值中减去1意味着在幅度上加1，IEEE-754二进制浮点格式使用符号幅度表示。这导致映射到float的IEEE-754binary32的floorf()的以下示例性实现：

float my_floorf (float a) 
{
const uint32_t FP32_SIGN_MASK = 0x80000000u;
const uint32_t FP32_EXPO_MASK = 0x7f800000u;
const uint32_t FP32_MANT_MASK = 0x007fffffu;
const uint32_t FP32_INT_BIT   = 0x00800000u;
const uint32_t FP32_NEG_ONE   = 0xbf800000u;
const uint32_t FP32_NEG_ZERO  = 0x80000000u;
const uint32_t FP32_ALL_ONES  = 0xffffffffu;
const uint32_t FP32_MAX_EXPO  = 128;
const uint32_t FP32_EXPO_NBIAS= (uint32_t)(-127);
const uint32_t FP32_NBRBITS_M1= 31;
const uint32_t FP32_STORED_MANT_BITS = 23;
uint32_t is_negative, gt_m1_ne_m0, has_fraction;
uint32_t s, t, ur, ua =  float_as_uint32 (a); 
s = ((ua & FP32_EXPO_MASK) >> FP32_STORED_MANT_BITS) + FP32_EXPO_NBIAS; 
t = (s > FP32_STORED_MANT_BITS) ? 
((s > FP32_MAX_EXPO) ? FP32_NBRBITS_M1 : 0) : 
(FP32_STORED_MANT_BITS - s); 
ur = ua & (FP32_ALL_ONES << t); 
is_negative = (ua & FP32_SIGN_MASK) >> FP32_NBRBITS_M1;
gt_m1_ne_m0 = is_negative & (s > FP32_MAX_EXPO) & ~(ua == FP32_NEG_ZERO);
has_fraction = ((FP32_STORED_MANT_BITS > s) & 
~((ua & (FP32_MANT_MASK >> s)) == 0));
ur = ((is_negative & has_fraction & ~gt_m1_ne_m0) ? (ur + (FP32_INT_BIT >> s)) : 
((gt_m1_ne_m0) ? FP32_NEG_ONE : 
ur));
return uint32_as_float (ur);
}

这里的一些操作是算术性质的，而不是位操作。我们记得，在二补码算术中，a-b=a+~b+1。我们还记得二进制加法是如何由和位向量和进位位向量组成的，其中进位位向量中的位的权重是和位向量中位的两倍：r=和+2*进位，其中和=a^b，进位=a&b.最后，我们记得，无符号比较是基于加法的执行。

这些基本事实允许我们构造辅助函数add32()、gtu32()和eq32()，用于位级运算的加法、无符号大于比较和相等比较。请注意，将(in-(相等与零进行比较是位级运算，因为它只需要将操作数的所有位进行"或"运算。有了仿真功能，上面floorf()的实现变成了以下内容：

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <math.h>
float uint32_as_float (uint32_t a)
{
float r;
memcpy (&r, &a, sizeof r);
return r;
}
uint32_t float_as_uint32 (float a)
{
uint32_t r;
memcpy (&r, &a, sizeof r);
return r;
}
uint32_t add32 (uint32_t a, uint32_t b)
{
uint32_t sum, carry;
carry = b;
do {
sum = a ^ carry;
carry = (a & carry) << 1;
a = sum;
} while (carry != 0);
return sum;
}
uint32_t gtu32 (uint32_t a, uint32_t b)
{
uint32_t r, s;
b = ~b;
s = a ^ b;
r = a & b;
s = s >> 1;
r = add32 (r, s);
return r >> 31;
}
uint32_t eq32 (uint32_t a, uint32_t b)
{
return (a ^ b) == 0;
}
float my_floorf_bit_ops_only (float a) 
{
const uint32_t FP32_SIGN_MASK = 0x80000000u;
const uint32_t FP32_EXPO_MASK = 0x7f800000u;
const uint32_t FP32_MANT_MASK = 0x007fffffu;
const uint32_t FP32_INT_BIT   = 0x00800000u;
const uint32_t FP32_NEG_ONE   = 0xbf800000u;
const uint32_t FP32_NEG_ZERO  = 0x80000000u;
const uint32_t FP32_ALL_ONES  = 0xffffffffu;
const uint32_t FP32_MAX_EXPO  = 128;
const uint32_t FP32_EXPO_NBIAS= (uint32_t)(-127);
const uint32_t FP32_NBRBITS_M1= 31;
const uint32_t FP32_MANT_BITS = 24;
const uint32_t FP32_STORED_MANT_BITS = 23;
uint32_t is_negative, gt_m1_ne_m0, has_fraction;
uint32_t s, t, ur, ua =  float_as_uint32 (a); 
s = add32 ((ua & FP32_EXPO_MASK) >> FP32_STORED_MANT_BITS, FP32_EXPO_NBIAS);
t = gtu32 (s, FP32_STORED_MANT_BITS) ? 
(gtu32 (s, FP32_MAX_EXPO) ? FP32_NBRBITS_M1 : 0) : 
add32 (FP32_MANT_BITS, ~s); 
ur = ua & (FP32_ALL_ONES << t); 
is_negative = (ua & FP32_SIGN_MASK) >> FP32_NBRBITS_M1;
gt_m1_ne_m0 = is_negative & gtu32 (s, FP32_MAX_EXPO) & ~eq32 (ua, FP32_NEG_ZERO);
has_fraction = (gtu32 (FP32_STORED_MANT_BITS, s) & 
~((ua & (FP32_MANT_MASK >> s)) == 0));
ur = ((is_negative & has_fraction & ~gt_m1_ne_m0) ? (add32 (ur, (FP32_INT_BIT >> s))) : 
((gt_m1_ne_m0) ? FP32_NEG_ONE : 
ur));
return uint32_as_float (ur);
}
int main (void)
{
uint32_t uarg, ures, uref;
float res, ref, arg;
uarg = 0x00000000;
do {
arg = uint32_as_float (uarg);
res = my_floorf_bit_ops_only (arg);
ref = floorf (arg);
ures = float_as_uint32 (res);
uref = float_as_uint32 (ref);
if (!((ures == uref) || (isnan (arg) && (ures == uarg)))) {
printf ("ERR: arg=%08x res=%08x ref=%08xn", uarg, ures, uref);
return EXIT_FAILURE;
}
uarg++;
} while (uarg);
return EXIT_SUCCESS;
}

在替代布置中，在计算trunc()的操作序列之前执行向floor()添加针对负输入的校正。这似乎导致行动总数大幅减少：

float my_floorf_alt (float a)
{
const uint32_t FP32_SIGN_MASK = 0x80000000u;
const uint32_t FP32_EXPO_MASK = 0x7f800000u;
const uint32_t FP32_MANT_MASK = 0x007fffffu;
const uint32_t FP32_NEG_ONE   = 0xbf800000u;
const uint32_t FP32_NEG_ZERO  = 0x80000000u;
const uint32_t FP32_POS_ZERO  = 0x00000000u;
const uint32_t FP32_ALL_ONES  = 0xffffffffu;
const uint32_t FP32_EXPO_NBIAS= (uint32_t)(-127);
const uint32_t FP32_MAX_EXPO  = 128;
const uint32_t FP32_NBRBITS_M1= 31;
const uint32_t FP32_STORED_MANT_BITS = 23;
uint32_t p0, p1, p2, s, mn, ur, ua =  float_as_uint32 (a);
s = ((ua & FP32_EXPO_MASK) >> FP32_STORED_MANT_BITS) + FP32_EXPO_NBIAS;
p0 = (ua & FP32_SIGN_MASK) >> FP32_NBRBITS_M1;
p1 = s > FP32_STORED_MANT_BITS;
p2 = s > FP32_MAX_EXPO;
mn = p0 ? FP32_NEG_ONE : FP32_POS_ZERO;
ur = p1 ? (p2 ? mn : ua) : (ua + (p0 ? (FP32_MANT_MASK >> s) : 0));
s = p1 ? ((ua == FP32_NEG_ZERO) ? FP32_NBRBITS_M1 : 0) : (FP32_STORED_MANT_BITS - s);
ur = ur & (FP32_ALL_ONES << s);
return uint32_as_float (ur);
}

Answer 2

这有时是可能的，前提是小数的表示是已知的，并且基于二进制记数(排除了DCB或定点十进制数(。

在IEEE浮点的情况下，您可以提取尾数和指数，并在此基础上通过位字段提取和移位(加上恢复初始位(获得整数部分。

不用说，这将是复杂的，低效的和很少可移植的。