[算法擂台]将float型变量转换为字符串，限C\C++
[算法擂台]将float型变量转换为字符串
打开CSDN倒处都是“某公司面试题”，今天我也来出一道，如果我是面试官，我会用这道题的。
目标：写一个函数，实现将float型变量转换为字符串的功能。
概念：
科学计数法的形式为a*(n^m)，前面的小数部分称为尾数，后面n^m中n称为底数，m称为阶数或指数
系统库指的是通常情况下编程环境默认提供的C标准库和STL
格式：
函数头定义如下。
int ftostr( char *pBuf, int nSize, float fNum )
float fTest = 54345.3435f;unsigned char *pData = (unsigned char*)&fTest;float fRes = 1.0f; // 表示1.xxx// 提取尾数for ( unsigned int i = 0; i < 23; ++i ){ // 确定尾数所在的字节，并计算当前的位在字节中的位置 unsigned char nBit = pData[ 2 - ( i + 1 ) / 8 ] << ( i + 1 ) % 8; nBit >>= 7; fRes += (float)nBit / ( 2 << i ); // 2<<i相当于2^i}// 提取阶码，阶码位于第30位到第23位unsigned char nExp = pData[3];nExp <<= 1; // 除掉附号位nExp |= ( pData[2] >> 7 ); // 与下个字节的首位合并，组成阶码nExp -= 0x7F; // 减127得到原阶数fRes *= pow( 2.0f, (float)*(char*)&nExp );// 提取符号位，位于最高位，第31位if ( pData[3] & 0x80 ){ // 最高位为1则为负，为0则为正 fRes = -fRes;}cout << setprecision(10) << fTest << "->" << fRes;//查表char table[] = "0123456789" ;//有效范围const int SCOPE = 10 ;int ftostr( char *pBuf, int nSize, float fNum ){ int i = 0 ; int cursor = 0 ; //如果是负数先转换为正数，添加负号 if (fNum < 0) { fNum = 0 - fNum ; *pBuf++ = '-' ; } //获取整数 i = fNum ; while (i) { pBuf[cursor++] = table[i%10] ; i /= 10 ; } //转换高低位 char c ; for(i; i < cursor/2 ; i++) { c = pBuf[i] ; pBuf[i] = pBuf[cursor-i-1] ; pBuf[cursor-i-1] = c ; } pBuf[cursor++] = '.' ; fNum -= int(fNum) ; i = nSize-cursor ; //获取小数 int scope = SCOPE - i > 0 ? i : SCOPE ; while (scope) { fNum *= 10 ; pBuf[cursor++] = table[(int)fNum] ; scope-- ; fNum -= int(fNum) ; }}
[解决办法]
别人的
; floating point to ASCII code
; author: R. Detmer
; revised: 4/98
.386
.MODEL FLAT
PUBLIC ftoaproc
C3 EQU 0100000000000000b
C2 EQU 0000010000000000b
C0 EQU 0000000100000000b
.DATA
value REAL4 ?
ten REAL4 10.0
one REAL4 1.0
round REAL4 0.000005
digit WORD ?
exponent WORD ?
controlWd WORD ?
byteTen BYTE 10
.CODE
ftoaproc PROC NEAR32 ; convert floating point number to ASCII string
; Parameters passed on the stack:
; (1) 32-bit floating point value
; (2) address of ASCII destination string
; ASCII string with format [blank/-]d.dddddE[+/-]dd is generated.
; (The string is always 12 characters long.)
push ebp ; establish stack frame
mov ebp, esp
push eax ; save registers
push ebx
push ecx
push edi
fstcw controlWd ; get control word
push controlWd ; save control word
or controlWd, 0000110000000000b
fldcw controlWd ; set control to chop
mov edi, [ebp+8] ; destination string address
mov eax, [ebp+12] ; value to convert
mov exponent, 0 ; exponent := 0
mov value, eax ; value to ST via memory
fld value
ftst ; value >= 0?
fstsw ax ; status word to AX
and ax, C0 ; check C0
jnz elseNeg ; skip if set (value negative)
mov BYTE PTR [edi], ' ' ; blank for positive
jmp endifNeg
elseNeg: mov BYTE PTR [edi], '-' ; minus for negative
fchs ; make number positive
endifNeg:
inc edi ; point at next destination byte
mov exponent, 0 ; exponent := 0
ftst ; value = 0?
fstsw ax ; status word to AX
and ax, C3 ; check C3
jne endifZero ; skip if zero
fcom ten ; value > 10?
fstsw ax ; status word to AX
and ax, C3 or C2 or C0 ; check for all C3=C2=C0=0
jnz elseLess ; skip if value not > 10
untilLess:
fdiv ten ; value := value/10
inc exponent ; add 1 to exponent
fcom ten ; value < 10
fstsw ax ; status word to AX
and ax, C0 ; check C0
jnz untilLess ; continue until value < 10
jmp endifBigger ; exit if
elseLess:
whileLess:
fcom one ; value < 1
fstsw ax ; status word to AX
and ax, C0 ; check C0
jz endwhileLess ; exit if not less
fmul ten ; value := 10*value
dec exponent ; subtract 1 from exponent
jmp whileLess ; continue while value < 1
endwhileLess:
endifBigger:
endifZero:
fadd round ; add rounding value
fcom ten ; value > 10?
fstsw ax ; status word to AX
and ax, C3 or C2 or C0 ; C3=C2=C0=0? (value > 10?)
jnz endifOver ; skip if not
fdiv ten ; value := value/10
inc exponent ; add 1 to exponent
endifOver:
; at this point 1.0 <= value < 10.0
fist digit ; store integer part
mov bx, digit ; copy integer to BX
or bx, 30h ; convert digit to character
mov BYTE PTR [edi], bl ; store character in destination
inc edi ; point at next destination byte
mov BYTE PTR [edi], '.' ; decimal point
inc edi ; point at next destination byte
mov ecx, 5 ; count of remaining digits
forDigit: fisub digit ; subtract integer part
fmul ten ; multiply by 10
fist digit ; store integer part
mov bx, digit ; copy integer to BX
or bx, 30h ; convert digit to character
mov BYTE PTR [edi], bl ; store character in destination
inc edi ; point at next destination byte
loop forDigit ; repeat 5 times
mov BYTE PTR [edi], 'E' ; exponent indicator
inc edi ; point at next destination byte
mov ax, exponent ; get exponent
cmp ax, 0 ; exponent >= 0 ?
jnge NegExp
mov BYTE PTR [edi], '+' ; non-negative exponent
jmp endifNegExp
NegExp: mov BYTE PTR [edi], '-' ; negative exponent
neg ax ; change exponent to positive
endifNegExp:
inc edi ; point at next destination byte
div byteTen ; convert exponent to 2 digits
or ax, 3030h ; convert both digits to ASCII
mov BYTE PTR [edi+1], ah ; store characters in destination
mov BYTE PTR [edi], al
pop controlWd ; restore control word
fldcw controlWd
pop edi ; restore registers
pop ecx
pop ebx
pop eax
pop ebp
ret 8
ftoaproc ENDP
END
[解决办法]
说实在的，我觉得是通过sprintf(szBuff, "%e", fNum),继而将字符串szBuff从'e'所在位置处分为两段，然后进一步根据要求加工下两段字符串就可以了，不过为了锻炼下，还是写了下面这段=(A_A)=
int ftostr( char *pBuf, int nSize, float fNum )
{
const ByteData cBLastBit = 0x01;
ByteData *pData = (ByteData *)&fNum;
ByteData bsign = (pData[3]>>7) & cBLastBit; // 获取符号位
char Order = ((pData[3]<<1) & 0xfe) | ((pData[2]>>7) & cBLastBit); // 获取阶数
Order -= 127;
double dMantissa = 1.0; // 尾数定义
double dFactor = 1.0; // 各尾数位所乘因子
for ( register short i = 1; i < 24; i++ )
{// 获取尾数
dFactor *= 0.5;
dMantissa += double((pData[2-(i>>3)]>>(7-i&7)) & cBLastBit) * dFactor;
}
// fMantissa * (2的Order次方) * (bsign? -1:0) == fNum
char Exp10 = 0;
if ( Order >= 0 )
{
for ( register short j = 0; j < Order; j++ )
{
if ( (dMantissa *= 2.0) < 10.0 )
continue;
dMantissa *= 0.1;
Exp10++;
}
}
else
{
for ( register short j = 0; j > Order; j-- )
{
if ( (dMantissa *= 0.5) >= 1.0 )
continue;
dMantissa *= 10.0;
Exp10--;
}
}
char ExpBuff[11];
memset( ExpBuff, 0, sizeof(ExpBuff) );
sprintf( ExpBuff, "*(10^%d)", Exp10 );
int iMinMantissaLen = 3; // 尾数最小长度：整数位（1）+小数点（1）+小数位（1）
if ( !bsign ) iMinMantissaLen++; // 如果浮点数为负数，则须加上符号位长度
if ( (int)strlen( ExpBuff ) + iMinMantissaLen + 1 > nSize )
return 0; // 注意字符串结束符"\0"
char MantissaBuff[9]; // float型数据位(6)+符号位(1)+小数点(1)+字符串结束符(1)
memset( MantissaBuff, 0, sizeof(MantissaBuff) );
dMantissa *= double( bsign? -1:1 );
sprintf( MantissaBuff, "%f", dMantissa );
int iMaxMantissaLen = nSize - (int)strlen( ExpBuff ) - 1;
if ( iMaxMantissaLen < (int)strlen(MantissaBuff) )
{
if ( MantissaBuff[iMaxMantissaLen] - '0' >= 5 )
{
// 舍入进位...注意舍入前一位为9的情况,特别是9.99...的情况
}
MantissaBuff[iMaxMantissaLen] = 0;
}
memset( pBuf, 0, nSize );
strcpy( pBuf, MantissaBuff );
strcat( pBuf, ExpBuff );
return strlen(pBuf);
}
[解决办法]
这个题其实用高级语言做不太合适,用汇编做反而比较简单.
算法其实不难,中心思想就是把二进制转化成BCD码来处理,而这个转换在高级语言层,很困难.
代码如下,未经严格测试,不保证完全正确:
#include <iostream>using std::cout;typedef unsigned int uint;typedef unsigned char byte;static const int FLOATPRC = 23;char bcdtable[23][24] = { "50000000000000000000000", "25000000000000000000000", "12500000000000000000000", "06250000000000000000000", "03125000000000000000000", "01562500000000000000000", "00781250000000000000000", "00390625000000000000000", "00195312500000000000000", "00097656250000000000000", "00048828125000000000000", "00024414062500000000000", "00012207031250000000000", "00006103515625000000000", "00000000000000000000000", "00000000000000000000000", "00000000000000000000000", "00000000000000000000000", "00000000000000000000000", "00000000000000000000000", "00000000000000000000000", "00000000000000000000000", "00000000000000000000000" };char bcdtablei[8][4] = { "001", "002", "004", "008", "016", "032", "064", "128"};void inibcdtable(){ for( int i = 0; i < FLOATPRC; ++ i ) { for( int j = 0; j < FLOATPRC; ++ j ) { bcdtable[i][j] -= '0'; } } for( int i = 0; i < 8; ++ i ) { for( int j = 0; j < 3; ++ j ) { bcdtablei[i][j] -= '0'; } }}//decimal addjust after addtionvoid daa( char* v, int n ){ int i = n; for( char* p = v+n; i--; ) { if( *p > 9 ) { *p -= 10; *(p-1) += 1; } --p; }}//add op2 to op1char* bcdadd( char* op1, const char* op2, int n ){ for( int i = 0; i < n; ++i ) { op1[i] = op1[i] + op2[i]; if( op1[i] > 9 ) { daa( op1, n ); } } return op1;}//decimal addjust befor divisionvoid dbd( char* v ){ int i = FLOATPRC; for( char* p = v; i-- > 1; ) { if( *p & 0x1 ) { *p &= 0xfe; *(p+1) += 10; } ++p; }}//bcd code divid 2char* bcddiv2( char* op ){ dbd( op ); for( int i = 0; i < FLOATPRC; ++i ) { op[i] = op[i] >> 1; } return op;}// ture bcd code to charactorvoid bac( char* v, int n ){ for( int i = 0; i < n; ++ i ) { v[i] += '0'; }}//turn a uint to bcdchar* inttobcd( char* buff, int size, byte v ){ memset( buff, 0, size ); for( int i = 0; i < 8 && v; ++i ) { if( v & 0x1 ) bcdadd( buff, bcdtablei[i], 3 ); v = v >> 1; } bac( buff, size ); return buff;}char* ftostr( char *pBuf, int nSize, float fNum ){ char* pbuf = pBuf; uint raw = *((uint*)&fNum); if( raw & 0x80000000 ) *pbuf++ = '-'; char buff[FLOATPRC+2];//1 for integal part, 1 for null terminator memset( buff, 0, FLOATPRC+2 ); //convert base to bcd code uint fpart = (raw & 0x7fffff) << 9; int i = 0; for ( ; i < 23 && fpart ; ++i ) { if( fpart & 0x80000000 ) { bcdadd( &buff[1], bcdtable[i], FLOATPRC ); } fpart = fpart << 1; } char p = (raw & 0x7f800000) >> 23; p -= 127; if( p == 0 ) { *pbuf++ = '1'; *pbuf++ ='.'; bac( buff, FLOATPRC ); strncpy( pbuf, buff + 1, i ); *(pbuf+i) = 0; } if( p > 0 ) { int power = 0; buff[0] = 1; while( p-- ) { bcdadd( buff, buff, FLOATPRC ); if( buff[0] > 9 ) { buff[0] -= 10; memmove( buff + 1, buff, FLOATPRC -1 ); buff[0] = 1; ++power; } } bac( buff, FLOATPRC); *pbuf++ = buff[0]; *pbuf++ = '.'; strncpy( pbuf, &buff[1], i ); pbuf += i; *pbuf++ = 'e'; inttobcd( pbuf, 3, power ); pbuf += 3; *pbuf++ = 0; } if( p < 0 ) { int power = 0; buff[0] = 1; while( p++ ) { bcddiv2( buff ); if( buff[0] < 1 ) { memmove( buff , buff + 1, FLOATPRC ); buff[FLOATPRC] = 0; ++power; } } if( buff[0] < 1 ) { memmove( buff , buff + 1, FLOATPRC ); buff[FLOATPRC] = 0; ++power; } bac( buff, FLOATPRC+1); *pbuf++ = buff[0]; *pbuf++ = '.'; strncpy( pbuf, &buff[1], i ); pbuf += i; *pbuf++ = 'e'; *pbuf++ = '-'; inttobcd( pbuf, 3, power ); pbuf += 3; *pbuf++ = 0; } return pBuf;}int main( int argc, char* argv ){ inibcdtable(); char buff[1000]; cout << ftostr( buff, 1000, 0.005 );}