前言

很久之前寫過一篇奶頭樂,關于簡單面試題總結.  重新翻閱看到這個題目.

/*
 * 寫一個函式 "將整數字串轉成整數"
 */

隨著代碼手感增強, 想為這個問題寫個終結者系列.  緬懷下曾經的自己. 

??

奇奇怪怪編碼 - https://www.emojiall.com/zh-hans/code/1F64F

正文

我們審視下這個問題, 整數字串轉成整數. 那么意味著有效字符僅有 "+-0123456789". 

其中整數常見有 short, int , long, long long 等對吧. 大部分人會寫成 string convert int. 

這里存在一個潛在模糊知識是, C 標準規定 sizeof(long long) >= sizeof (long) >= sizeof(int) >= sizeof(short).

但沒有明說具體多大, 這就意味著不同平臺實作上可以自由發揮. 例如 sizeof (long) 多數 linux 平臺是 8, window 是 4.

所以這里不寫那么復雜. 簡單點 string convet int32.

因此寫題目開始可以和對方一塊交流探討下. 有了 string convert int32 經驗加一些平臺分支宏搞出 string convert int 也容易. 

那我們開始吧. 

相關素材 : https://github.com/wangzhione/temp/blob/master/code/offer1/67_string_int.c#L17-L75

#include <stdio.h>
#include <limits.h>
#include <stddef.h>
#include <stdint.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

/* describe : 

   寫一個完整 string to int32_t
 */

#define NUMBER_SUCCESS  0    // 轉換成功
#define NUMBER_INVALID -2    // 非法字符
#define NUMBER_BORDER  -3    // 數值越界

int str2int32(const char * str, int32_t * res) {
    if (str == NULL) {
        return NUMBER_INVALID;
    }

    if (*str == 0) {
        if (res) *res = 0;
        return NUMBER_SUCCESS;
    }

    // int32_t    int    Signed    32    4    -2,147,483,648    2,147,483,647
    // + - 1 位元組, 后面 max size = 10
    // 如果 max size = 10, 那么 max size = 9 的時候最大值為 2,147,483,64

    int32_t num = 0;
    bool minus = false; // 標識負數
    if (*str == '+' || *str == '-') {
        minus = *str++ == '-';
    }

    char c;
    int count = 0;
    while (++count < 10 && (c = *str++) != 0) {
        if (c >= '0' && c <= '9') {
            // 合理字符
            num = 10 * num + c - '0';
        } else {
            return NUMBER_INVALID;
        }
    }
    if (c != 0) {
        if (num > 214748364) {
            // size = 9 時候最大值
            return NUMBER_BORDER;
        }
        c = *str++;
        if (*str != 0) {
            // size > 10 越界
            return NUMBER_BORDER;
        }
        if ((c >= '0' && c <= '7') || (c == '8' && minus)) {
            if (c == '8') {
                if (res) *res = -2147483648;
                return NUMBER_SUCCESS;
            }
            num = 10 * num + c - '0';
        } else {
            return NUMBER_BORDER;
        }
    }

    num = minus ? -num : num;
    if (res) *res = num;
    return NUMBER_SUCCESS;
}


// build:
// gcc -g -O3 -Wall -Wextra -Werror -o 67_string_int 67_string_int.c
//
int main(void) {
    int code;
    int32_t num;
    const char * str;

    num = 0;
    str = NULL;
    code = str2int32(str, &num);
    printf("code = %d, str = %s, num = %d\n", code, str, num);
    assert(code == NUMBER_INVALID && num == 0);

    num = 0;
    str = "-1";
    code = str2int32(str, &num);
    printf("code = %d, str = %s, num = %d\n", code, str, num);
    assert(code == NUMBER_SUCCESS && num == -1);

    num = 0;
    str = "1234A";
    code = str2int32(str, &num);
    printf("code = %d, str = %s, num = %d\n", code, str, num);
    assert(code == NUMBER_INVALID);

    num = 0;
    str = "2147483647";
    code = str2int32(str, &num);
    printf("code = %d, str = %s, num = %d\n", code, str, num);
    assert(code == NUMBER_SUCCESS && num == 2147483647);

    num = 0;
    str = "-2147483648";
    code = str2int32(str, &num);
    printf("code = %d, str = %s, num = %d\n", code, str, num);
    assert(code == NUMBER_SUCCESS && num == -2147483648);

    num = 0;
    str = "-2147483649";
    code = str2int32(str, &num);
    printf("code = %d, str = %s, num = %d\n", code, str, num);
    assert(code == NUMBER_BORDER);

    num = 0;
    str = "2147483648";
    code = str2int32(str, &num);
    printf("code = %d, str = %s, num = %d\n", code, str, num);
    assert(code == NUMBER_BORDER);

    exit(EXIT_SUCCESS);
}

整體代碼分兩部分實作 str2int32 和 assert 單元測驗 . 單元測驗怎么強調都不為過, 這是成為高手必經之路.

其中實作圍繞核心思路是下面這些數學知識. 

int32_t    int    Signed    32    4    -2,147,483,648    2,147,483,647

實作層面沒有借助 long 來判斷越界, 當然這種做法前頭已經說了, 存在潛在問題, 不推薦.  

這類資料轉換函式很多是跨學科, 對于普通工程師而言有點吃力, 感謝相關科學家或專業人士鑄就了今天的基礎. 

希望以上思路能終結這個面試題. 歡迎大家補充更優更完備解法. 

標籤：其他

上一篇：Java案例之評委打分

下一篇：【論文考古】量化SGD QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding