Перебор всех целых чисел без знака в цикле for

Question

Допустим, я хочу перебрать все целые числа в for петля. Для обсуждения предположим, что я вызываю неизвестную функцию f(unsigned x) для каждого целого числа:

for (unsigned i = 0; i < UINT_MAX; i++) {
     f(i);
}

Конечно, вышеупомянутое не в состоянии перебрать все целые числа, потому что оно пропускает одно: UINT_MAX. Изменение условия на i <= UINT_MAX просто приводит к бесконечному циклу, потому что это тавтология.

Вы можете сделать это с do-while петля, но вы теряете все тонкости for синтаксис.

Можно мне свой торт (for циклы) и есть это тоже (перебрать все целые числа)?

Answer 1

Вы можете сделать это с помощью цикла do-while, но вы потеряете все тонкости синтаксиса for.

Это все еще выполнимо с циклом do-while, используя анонимную область блока:

{
    unsigned i = 0;
    do { f(i); } while (++i != 0);
}

Хотя эта конструкция может быть не самой идиоматической, она является очевидным кандидатом на четкий код сборки. Например, gcc -O компилирует это как:

.L2:
        mov     edi, ebx   ; ebx starts with zero
        call    f
        add     rbx, 1
        cmp     rbx, rbp   ; rbp is set with 4294967296
        jne     .L2

Answer 2

Вам придется выполнить тест в конце тела цикла, очень похоже на do-while:

for (unsigned int i = 0; /* nothing */; i++) {
    ...
    if (i == UINT_MAX) {
        break;
    }
}

Чтобы тест в стандарте для положения проверки цикла работал, вам необходимо отслеживать текущую итерацию таким образом, чтобы можно было различить состояния UINT_MAX+2: по одному для каждого ввода тела цикла и по одному нет. Один беззнаковый int не может справиться с этим, поэтому вам понадобится хотя бы одна вспомогательная переменная или больший счетчик цикла.

Answer 3

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

for (unsigned int i = 0, repeat = 0; !(i == 0 && repeat); i++, repeat = 1) {
    ...
}

Answer 4

Классический способ эффективной реализации итерации с помощью одного теста - это do / while цикл:

unsigned i = 0;
do { f(i); } while (i++ != UINT_MAX);

Если вы настаиваете на использовании for цикл:

for (unsigned i = 0;; i++) {
    f(i);
    if (i == UINT_MAX)
        break;
}

Вот еще один вариант с 2 переменными, где вся логика находится внутри for выражения:

for (unsigned int i = 0, not_done = 1; not_done; not_done = (i++ - UINT_MAX)) {
    f(i);
}

Это может привести к более медленному коду из-за дополнительной переменной, но, как прокомментировал BeeOnRope, clang а также icc скомпилируйте его в очень эффективный код.

Answer 5

Простое решение было бы,

unsigned i;
for (i=0; i<UINT_MAX; i++) {
  f(i);
}
f(i);  // i will be UINT_MAX at this time.

Answer 6

Используйте больший целочисленный тип:

#include <limits.h>
#include <stdio.h>

int main() {
    for (unsigned long i = 0; i <= UINT_MAX; i++) {
        f(i);
    }
}

Эта версия использует stdint для большей согласованности

#include <stdio.h>
#include <stdint.h>

int main() {
    for (uint_fast64_t i = 0; i <= UINT32_MAX; ++i) {
        f(i);
    }
}