C реализация strlen() в одной строке кода

Вчера был на собеседовании и попросили реализовать strlen() на C без использования стандартных функций, все руками. Как абсолютный любитель, я реализовал примитивную версию с циклом while. Глядя на это, мой интервьюер сказал, что это можно реализовать всего одной строкой кода. В тот момент я не мог создать этот код, используя этот термин. После собеседования я спросил своих коллег, и самые опытные из них дали мне эту штуку, которая действительно отлично работала:

size_t str_len (const char *str)
{
    return (*str) ? str_len(++str) + 1 : 0;
}

Так вот вопрос, можно ли без использования рекурсии, и если да, то как? Условия:

  • без всякого ассемблера
  • без каких-либо функций C, существовавших в библиотеках
  • без написания нескольких строк кода в одном

Обратите внимание, что это не вопрос оптимизации или реального использования, а просто возможность сделать задачу выполненной.


person Alex    schedule 19.03.2014    source источник
comment
Это, вероятно, лучше для кода гольфа   -  person Petesh    schedule 20.03.2014
comment
Одна строка — довольно свободное требование.   -  person hatchet - done with SOverflow    schedule 20.03.2014
comment
Возможность реализовать strlen() в одной строке довольно бессмысленна. Я бы никогда никого не попросил сделать это в интервью или как-то иначе.   -  person gnasher729    schedule 20.03.2014
comment
@gnasher729: Согласен. С другой стороны, большинство вопросов-головоломок на собеседовании довольно бессмысленны, за исключением возможности посмотреть, как работает мозг кандидата... при условии, что у него еще нет готового ответа, и в этом случае это ничего не говорит вам, кроме того, что у него есть некоторый опыт.   -  person keshlam    schedule 20.03.2014
comment
@кешлам, согласен с тобой. Похоже было дело посмотреть мое поведение в этой ситуации   -  person Alex    schedule 20.03.2014
comment
В C++ вы можете использовать хвостовую рекурсию: size_t strlen(const char *str, size_t acc = 0) { return *str ? strlen(str+1, acc + 1) : acc; } Это должно быть скомпилировано в цикл, я думаю   -  person Niklas B.    schedule 20.03.2014


Ответы (9)


Подобно ответу @DanielKamilKozar, но с циклом for вы можете сделать это без тела цикла for, и len правильно инициализируется в функции:

void my_strlen(const char *str, size_t *len)
{
    for (*len = 0; str[*len]; (*len)++);
}
person Digital Trauma    schedule 19.03.2014
comment
А, очень умно! И так очевидно. - person Daniel Kamil Kozar; 20.03.2014
comment
А как насчет for (*len = 0; *str; ++str, (*len)++);? Таким образом, вам не нужно разыменовывать len для индексации str на каждой итерации. - person Remy Lebeau; 20.03.2014
comment
@RemyLebeau Да, это тоже сработает. Я предполагаю, что если бы вы оптимизировали это, вам нужно было бы профилировать, что быстрее из уважения или дополнительного приращения. В любом случае компилятор, скорее всего, поместит в регистры как str, так и len, поэтому, вероятно, в любом случае это не имеет большого значения. - person Digital Trauma; 20.03.2014
comment
прототип strlen size_t strlen (const char *str) - person technosaurus; 20.01.2017
comment
Это не та же подпись, что и strlen. - person n. 1.8e9-where's-my-share m.; 19.03.2017
comment
@RemyLebeau Обычно приращение в любом случае эффективно разыменовывает len. Так что это то же самое, но все это не имеет значения, потому что пока len и *str находятся в L1, это будет проходить через строку с максимальной скоростью. - person pmttavara; 17.02.2018

Лучшее, что я мог придумать, это это, но это не стандартный strlen, так как сама функция имеет другой прототип. Кроме того, предполагается, что *len в начале равно нулю.

void my_strlen(const char *str, size_t *len)
{
        while(*(str++)) (*len)++;
}

Мне любопытно, как стандартный strlen может быть реализован в «одной строке кода», потому что для этого потребуется return, который является «одной строкой кода», судя по тому, что вы опубликовали.

Тем не менее, я согласен с комментариями о том, что это невероятно глупый вопрос для интервью.

person Daniel Kamil Kozar    schedule 19.03.2014

Если это не обязательно должна быть функция, этот однострочный код, вероятно, является самым простым и коротким способом вычисления длины любого массива с завершающим нулем (не включая объявления переменных и печать):

int main() {
    const char *s = "hello world";
    int n = 0;

    while (s[++n]);

    printf ("%i\n", n);
    return 0;
}

если это должна быть функция, то у вас не может быть точной подписи функции как strlen(), так как возврат должен быть в отдельной строке. В противном случае вы можете сделать это:

void my_strlen(int* n, const char* s) {
    while (s[++(*n)]);
}

int main() {
    const char *s = "hello world";
    int n = 0;

    my_strlen(&n, s);

    printf ("%i\n", n);
    return 0;
}
person Lie Ryan    schedule 20.03.2014
comment
Ваш цикл while подсчитывает нулевой терминатор, поэтому длина всегда будет на +1 больше, чем strlen() вернет. Вместо этого вам придется использовать while (s[n]) ++n;, чтобы учесть это. - person Remy Lebeau; 20.03.2014
comment
Это исправление привело к неопределенному поведению для строк размера 0. Строка размера 0 является допустимой строкой, и strlen в этом случае также не будет ошибкой. Реми Лебо предоставил правильное решение. - person IInspectable; 03.03.2017
comment
Вот еще несколько способов ее решения: if (*s) while (s[++n]);; while (s[n++]); n--;; for (n = -1; s[++n];);. - person pmttavara; 18.02.2018

Кажется, это работает нормально.

unsigned short strlen4(char *str)
{
    for (int i = 0; ; i++) if (str[i] == '\0') return i;
}

Есть предположения?

ОБНОВИТЬ!

Это, вероятно, самый эффективный способ реализации strlen. Большинство компиляторов так или иначе используют его.

Это может быть немного сложнее понять, особенно если вы не изучили указатели.

size_t strlen(char *str)
{
    register const char *s;
    for (s = str; *s; ++s);
    return(s - str);
}
person ChrisK    schedule 18.11.2015
comment
Я закодировал это давным-давно, я мог бы сделать лучшую реализацию в любое время! :D - person ChrisK; 20.01.2017
comment
Мне любопытно, какая у вас лучшая реализация? (Кстати, я только что заметил, что кто-то другой опубликовал тот же ответ.) - person Saiph; 20.01.2017
comment
register переменные? Опять 1994 год? - person Daniel Kamil Kozar; 03.06.2019

Как насчет пустого цикла for. Нравится

int i=0;
for(; str[i]!=0; ++i);
person user1404617    schedule 19.03.2014
comment
Это не полная функция. Где return? - person Daniel Kamil Kozar; 20.03.2014
comment
@DanielKamilKozar Отредактировано. Счетчик должен быть инициализирован вне цикла. Но он все еще считает это одной строкой!? - person user1404617; 20.03.2014
comment
Это не делает функцию strlen, поэтому она не считается, если это то, что нужно. - person user1404617; 20.03.2014
comment
это похоже на две строки - person Alexey Malistov; 20.03.2014

Вопреки тому, что говорят другие, это невозможно, если соблюдаются некоторые разумные ограничения. Ограничения:

  • один непустой оператор или объявление в теле функции (составной оператор с непустым телом — это как минимум два оператора в сумме)
  • такая же подпись, как у настоящего strlen
  • нет рекурсии

Любая функция с сигнатурой strlen должна иметь оператор возврата. Оператор return состоит из ключевого слова return и выражения. В языке C нет выражений, выполняющих циклы. Для этого нужен оператор, но эта позиция зарезервирована для оператора возврата.

Если ослабить эти ограничения (скажем, изменить сигнатуру или не учитывать операторы return и/или объявления и/или тела составных операторов, пока они «просты», как отдельные «строки»), задача становится возможной и довольно просто, как можно увидеть во многих примерах здесь и во всем Интернете.

person n. 1.8e9-where's-my-share m.    schedule 19.03.2017
comment
Как это size_t strlen (const char *s) { for (auto p = s;; ++p) if (!*p) return p - s; } не одно утверждение? - person pmttavara; 19.02.2018
comment
@pmtavara Я насчитываю три утверждения (for, if и return). И, пожалуйста, позвоните мне, когда у C будет auto. - person n. 1.8e9-where's-my-share m.; 19.02.2018
comment
Это своего рода неработоспособное ограничительное определение утверждения. - person pmttavara; 19.02.2018
comment
@pmtavara, если вы не считаете вложенные операторы операторами, вы можете просто обернуть все в блок и положить этому конец. - person n. 1.8e9-where's-my-share m.; 19.02.2018
comment
Это не вложенные операторы, это составные операторы. p = s; p++;, очевидно, состоит из двух утверждений. if (*p) p = s; — это оператор управления с простым оператором. Я не говорю, эй, смотри, это одна строка, потому что я удалил все символы новой строки. - person pmttavara; 19.02.2018

size_t strlen (const char* str) {
    for (const char* s1 = str; ; s1++) if (!(*s1)) return s1 - str; 
}

По сравнению с str[i], приведенный выше код, который увеличивает указатель, будет работать лучше, потому что индексирование str[i] будет оцениваться как: *(str + i), что является операцией сложения, выполняемой с каждым циклом, в то время как операция увеличения выполняется быстрее .

Кроме того, по сравнению с strlen(const char *str, size_t *len) нет необходимости в дополнительном параметре, который может предоставить вызывающая сторона.

Наконец, это на одной строке в соответствии с исходным запросом.

person Tamer Mahfouz    schedule 19.03.2017
comment
Хотя этот код может дать ответ на вопрос, предоставление дополнительного контекста относительно того, как и/или почему он решает проблему, улучшит долгосрочную ценность ответа. - person Donald Duck; 19.03.2017
comment
По сравнению с str[i] код, который увеличивает указатель, будет работать лучше, потому что индексирование str[i] будет оцениваться как: *(str + i), что является операцией сложения, выполняемой с каждым циклом, в то время как операция увеличения выполняется быстрее. Кроме того, по сравнению с strlen(const char *str, size_t *len) нет необходимости в дополнительном параметре, который может предоставить вызывающая сторона. Наконец, это на одной строке в соответствии с исходным запросом. - person Tamer Mahfouz; 20.03.2017
comment
Добавлено в ответ. - person Tamer Mahfouz; 20.03.2017

Собственный код

unsigned int strlen(const char *s)
{
    int l;for(l=0;s[l]!='\0';l++);return l;
}

Вы можете заменить '\0' на ноль, но я предпочитаю так

Надеюсь, поможет.

person Community    schedule 24.08.2017

person    schedule
comment
Я бы использовал это: for (size_t len = 0; ; ++str, ++len) { if (!*str) return len; } - person Remy Lebeau; 20.03.2014
comment
обратите внимание на критерии: without just spelling few strings of code in one - person Lie Ryan; 20.03.2014
comment
Строки заканчиваются символом новой строки... возможно, вы думаете об утверждениях - person M.M; 20.03.2014
comment
+1 Учитывая, насколько расплывчато был сформулирован вопрос, я думаю, что это лучший ответ: он сохраняет как функциональность, так и сигнатуру strlen(), и, возможно, это делается в одной строке. - person lapk; 20.03.2014
comment
@MattMcNabb: технически вы правы, и описание проблемы определенно можно было бы перефразировать, чтобы оно было более точным; но помещение трех утверждений в одну строку явно не соответствует цели вопроса IMO. - person Lie Ryan; 20.03.2014
comment
@Лив Райан: где ты видишь несколько строк? Это одно утверждение for(... ; ... ; ...) ...; - person Alexey Malistov; 20.03.2014
comment
@Alex: Совершенно очевидно, что реализация представляет собой одну строку кода. Это также одно заявление. Он состоит из нескольких выражений, но также и ваша рекурсивная реализация, которая, по-видимому, соответствует постановке задачи. Этот ответ действительно единственный, который реализует strlen в одной строке кода. Ваш принятый ответ не реализует strlen, а скорее то, что можно вызвать для вычисления длины строки с нулевым завершением. - person IInspectable; 03.03.2017