Question

Hàm strlen trong C hoạt động như thế nào?

1

823214 • 20 đã đăng:

lập trình c (ngôn ngữ lập trình) strlen (ngôn ngữ c)

• •

đã hỏi 5.7 năm trước bởi

823214 • 20

thêm bình luận...

xuans2huy đã đăng 5.7 năm trước bởi xuans2huy • **510** · Answer 1

1

xuans2huy • 510 đã đăng:

Trước tiên, bạn nên biết chuỗi trong C chuẩn được định nghĩa và lưu trữ như thế nào:

A string is defined as a contiguous sequence of characters terminated by the first null character.

--- ISO Standard ---

Tạm dịch chuỗi là dãy liên tiếp những ký tự mà kết thúc bằng ký tự null, ký tự null ở đây là ký tự \0. Vậy khi bạn khai báo một chuỗi trong C như sau,

char str[] = "Welcome";

hoặc

char *str = "Welcome";

Thì trình biên dịch sẽ tự động thêm ký tự null \0 vào sau cùng của chuỗi, do đó, trong bộ nhớ chuỗi sẽ được lưu dưới dạng mảng các ký tự như sau,

Cách chuỗi được lưu trữ trong bộ nhớ C

Hàm strlen() trong C sẽ bắt đầu duyệt từ vị trí đầu mảng của chuỗi cho đến khi gặp ký tự \0 thì dừng, đồng thời đếm số lần duyệt và trả về độ dài của chuỗi mà không bao gồm ký tự \0,

#include <stdio.h>
#include <string.h>

int main(){
    char *str = "Welcome";
    int strLenght = strlen(str);
    printf("Chieu dai cua chuoi <%s> la: %d\n", str, strLenght); // Chieu dai cua chuoi <Welcome> la: 7
}

Cú pháp của hàm strlen() trong C như sau,

size_t strlen(const char *str);

Ý tưởng thuật toán strlen thuở sơ khai ban đầu,

size_t strlen(const char *str){
    size_t i = 0;
    for(i; str[i] != '\0'; i++); // Duyệt mảng, gặp ký tự '\0' thì dừng,
                                       // mỗi lần duyệt, tăng i 1 đơn vị.
    return i;
}

Thuật toán strlen được tối ưu hóa,

size_t strlen(const char *str){
    const char *s = str; // Sao chép cạn, tức s và str cùng giữ 1 địa chỉ ban đầu.

    while (*s) s++; // Duyệt đến khi con trỏ s trỏ null, tức là gặp ký tự \0,
                           // lúc này con trỏ s đang nắm giữ địa chỉ tại vị trí null.

    return s - str; // Lấy địa chỉ tại vị trí null trừ địa chỉ khi bắt đầu chuỗi,
                        // ta được độ dài của chuỗi.
}

•

đã đăng 5.7 năm trước bởi

xuans2huy • 510

đã bổ sung 5.7 năm trước bởi

xuans2huy • 510

Vẫn còn có thể tối ưu hóa tốc độ thực thi của hàm strlen bằng cách sử dụng các toán tử thao tác trên bits và thậm chí có thể tối ưu hóa thêm chút nữa bằng hợp ngữ.

Do đó, mã nguồn thực tế đã được tối ưu hóa ở mức rất cao, không còn đơn giản như trên nữa, đoạn code bên dưới mình lấy từ chính cách cài đặt thư viện strlen() của ngôn ngữ C ở ngoài thực tế (glibc-2.28), bạn có thể tìm thấy tại GNU Libc theo đường dẫn glibc-2.28/string/strlen.c/

#include <string.h>
#include <stdlib.h>

#undef strlen

#ifndef STRLEN
# define STRLEN strlen
#endif

/* Return the length of the null-terminated string STR.  Scan for
   the null terminator quickly by testing four bytes at a time.  */
size_t
STRLEN (const char *str)
{
  const char *char_ptr;
  const unsigned long int *longword_ptr;
  unsigned long int longword, himagic, lomagic;

  /* Handle the first few characters by reading one character at a time.
     Do this until CHAR_PTR is aligned on a longword boundary.  */
  for (char_ptr = str; ((unsigned long int) char_ptr
            & (sizeof (longword) - 1)) != 0;
       ++char_ptr)
    if (*char_ptr == '\0')
      return char_ptr - str;

  /* All these elucidatory comments refer to 4-byte longwords,
     but the theory applies equally well to 8-byte longwords.  */

  longword_ptr = (unsigned long int *) char_ptr;

  /* Bits 31, 24, 16, and 8 of this number are zero.  Call these bits
     the "holes."  Note that there is a hole just to the left of
     each byte, with an extra at the end:

     bits:  01111110 11111110 11111110 11111111
     bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD

     The 1-bits make sure that carries propagate to the next 0-bit.
     The 0-bits provide holes for carries to fall into.  */
  himagic = 0x80808080L;
  lomagic = 0x01010101L;
  if (sizeof (longword) > 4)
    {
      /* 64-bit version of the magic.  */
      /* Do the shift in two steps to avoid a warning if long has 32 bits.  */
      himagic = ((himagic << 16) << 16) | himagic;
      lomagic = ((lomagic << 16) << 16) | lomagic;
    }
  if (sizeof (longword) > 8)
    abort ();

  /* Instead of the traditional loop which tests each character,
     we will test a longword at a time.  The tricky part is testing
     if *any of the four* bytes in the longword in question are zero.  */
  for (;;)
    {
      longword = *longword_ptr++;

      if (((longword - lomagic) & ~longword & himagic) != 0)
    {
      /* Which of the bytes was the zero?  If none of them were, it was
         a misfire; continue the search.  */

      const char *cp = (const char *) (longword_ptr - 1);

      if (cp[0] == 0)
        return cp - str;
      if (cp[1] == 0)
        return cp - str + 1;
      if (cp[2] == 0)
        return cp - str + 2;
      if (cp[3] == 0)
        return cp - str + 3;
      if (sizeof (longword) > 4)
        {
          if (cp[4] == 0)
        return cp - str + 4;
          if (cp[5] == 0)
        return cp - str + 5;
          if (cp[6] == 0)
        return cp - str + 6;
          if (cp[7] == 0)
        return cp - str + 7;
        }
    }
    }
}
libc_hidden_builtin_def (strlen)

Mình còn gà mờ nên chỉ hiểu được một phần đầu ở đoạn mã nguồn trên, hy vọng sẽ có ích cho những bạn nào muốn tham khảo sâu cách hàm strlen trong C hoạt động.

– Minh Danh 16.08.2018

Yup, nhưng mình nghĩ cỡ trình độ chúng ta nên dừng lại ở ý tưởng và đoạn mã nguồn mẫu đơn giản là đủ ^^, đào sâu vào rất tốn kém thời gian để hiểu, tác giả viết ngôn ngữ C đã là những bậc thầy rồi, hiểu cách họ viết mã nguồn cũng cả là một vấn đề về kiến thức lẫn kinh nghiệm, dù sao cũng cảm ơn bạn đã bổ sung nhé.

– xuans2huy 16.08.2018

1

Đôi khi tham khảo cách viết mã nguồn của những người bậc thầy cũng có ích đấy bạn à, bạn có cơ hội được tiếp xúc với mã nguồn thực tế hơn là những mã nguồn vô cùng đơn giản chỉ vừa đủ để thể hiện ý tưởng khi chúng ta đang học.

– Minh Danh 16.08.2018

Xin ghi nhận ý kiến của bạn.

– xuans2huy 16.08.2018

thêm bình luận...