此功能被發現here。它的strcmp
實現:優化的strcmp實現
int strcmp(const char* s1, const char* s2)
{
while (*s1 && (*s1 == *s2))
s1++, s2++;
return *(const unsigned char*)s1 - *(const unsigned char*)s2;
}
我明白所有,但最後一行,總之什麼是在最後一行回事?
此功能被發現here。它的strcmp
實現:優化的strcmp實現
int strcmp(const char* s1, const char* s2)
{
while (*s1 && (*s1 == *s2))
s1++, s2++;
return *(const unsigned char*)s1 - *(const unsigned char*)s2;
}
我明白所有,但最後一行,總之什麼是在最後一行回事?
return *(const unsigned char*)s1-*(const unsigned char*)s2;
OP:簡而言之,最後一行發生了什麼?
答:比較第一個潛在的字符串差異。根據規範要求,chars
均被引用爲unsigned char
。 2被提升爲int
,並返回差異。
注:
1的返回值的符號(< 0,0,> 0)是最有意義的部分。它是C規範唯一指定的部分。
2在某些系統上char
是signed
(更常見)。其他人,char
是unsigned
。定義最後比較的「標誌性」可促進可移植性。請注意,fgetc()
獲得字符爲unsigned char
。
3除此之外,字符串以\0
結尾,所採用的字符編碼(如ASCII - 最常見)在二進制級別上沒有區別。如果兩個字符串中的第一個char
s值爲65和97,則即使字符編碼爲非ASCII,第一個字符串也會小於第二個字符串。OTOH,strcmp("A", "a")
將返回一個負數時字符編碼是ASCII,而是可以以不同的字符編碼返回一個正數爲他們的潛在價值和爲了不被C.
strcmp
返回哪個字符串是大於另一方面,不只是它們是否相等。
最後一行減去第一個不匹配的字符,看哪個更大。如果整個字符串匹配,那麼它將是0-0=0
,它給出了「相等」的結果。
這種實現是不是真的很好的優化,因爲這將需要彙編代碼和高速緩存行的知識,負荷大小等
此實現絕對不是最優化的內置的strcmp
,它只是另一種實現,我相信它可能會比內置版本更差。
如果比較值相等,比較函數應該返回0,如果第一個值較小,則比較函數返回任何負數,如果第一個值較大,則比較函數返回任意正數。這就是最後一行發生的事情。
最後一行的想法是將字符轉換爲無符號字符,我相信作者意思是爲了在標準字符(ASCII代碼0-127)之後對非標準字符進行排序。
編輯:代碼中沒有錯誤,如果s1
指向的值小於s2
指定的值,則在代碼爲128及以上的字符之前排序標準字符,它可以並且將返回負值。
即使轉換爲int? –
是的,我想知道爲什麼演員在那裏。那麼strcmp的真正實現是什麼? –
@ el.pescado轉換爲int將在計算值後發生。該值已經下溢0. –
我preffer此代碼:
int strcmp(const char *str1, const char *str2)
{
int s1;
int s2;
do {
s1 = *str1++;
s2 = *str2++;
if (s1 == 0)
break;
} while (s1 == s2);
return (s1 < s2) ? -1 : (s1 > s2);
}
爲它的ARMv4編譯如下:
strcmp:
ldrsb r3, [r0], #1 ;r3 = *r0++
ldrsb r2, [r1], #1 ;r2 = *r1++
cmp r3, #0 ;compare r3 and 0
beq @1 ;if r3 == 0 goto @1
cmp r3, r2 ;compare r3 and r2
beq strcmp ;if r3 == r2 goto strcmp
;loop is ended
@1:
cmp r3, r2 ;compare r3 and r2
blt @2 ;if r3 < r2 goto @2
movgt r0, #1 ;if r3 > r2 r0 = 1
movle r0, #0 ;if r3 <= r2 r0 = 0
bx lr ;return r0
@2:
mov r0, #-1 ;r0 = -1
bx lr ;return r0
正如你可以看到有6只在循環下指令+末atmost 5個指令。所以複雜度是6 *(strlen + 1)+ 5.
移動(s1 == 0)到while條件會導致更糟糕的ARM代碼(我不知道爲什麼)。
您應該將字符轉換爲無符號字符:'s1 =(unsigned char)* str1 ++;'以實現'strcmp()'的確切語義。 – chqrlie
該實現可以進一步優化,削去一些比較:
int strcmp(const char *s1, const char *s2) {
unsigned char c1, c2;
while ((c1 = *s1++) == (c2 = *s2++)) {
if (c1 == '\0')
return 0;
}
return c1 - c2;
}
返回值是0
如果字符串是相同的直至幷包括終止空字節。返回值的符號是第一個不同字符之間的差值,按照C標準轉換爲unsigned char
。
如果char
比int
,這是真正的所有,但一些罕見的嵌入式系統要小,這種差異可以用一個簡單的減法來計算,兩者c1
和c2
被晉升爲int
與此不同的是保證適合在int
的範圍內。
在哪裏sizeof(int) == 1
,返回值應計算這樣的系統:
return (c1 < c2) ? -1 : 1;
沒有什麼「優化」這個執行。 –