Являются ли побитовые операторы медленнее, чем обычные циклы, такие как цикл for?

Измерение с помощью pow():

• Как уже отмечалось, бенчмаркинг Leetcode совсем не точен.

• Мы можем смоделировать каждую функцию и просто рассчитать время с помощью std::chrono::steady_clock::now(); и увидеть общий обзор измерений, который показывает, что решение bitwise() работает намного быстрее:

#include <iostream>
#include <chrono>
#include <cmath>

bool bitwise(const int n)
{
    return n > 0 && (n & (n - 1)) == 0;
}

bool forloop(const int n)
{
    for (int i = 0; i <= 30; i++)
    {
        int ans = std::pow(2, i);
        if (n == ans)
        {
            return true;
        }
    }
    return false;
}

template <typename Func>
long long timeit_with_steady_clock(Func F, int it)
{
    auto start = std::chrono::steady_clock::now();
    for (int i = 0; i < it; i++)
    {
        F(i);
    }
    auto end = std::chrono::steady_clock::now();
    return std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
}

int main()
{
    const int it = 10000000;
    auto A = timeit_with_steady_clock(bitwise, it);
    auto B = timeit_with_steady_clock(forloop, it);
    std::cout << A << " ms vs. " << B << " ms" << "\n";

    return 0;
}

Принты

28 ms vs. 6705 ms

Измерение без использования pow():

• Если мы удалим pow(), решение bitwise() будет примерно в 17 раз быстрее, чем решение forloop(), что хорошо объяснено в этом ответе:

#include <iostream>
#include <chrono>

bool bitwise(const int n)
{
    return n > 0 && (n & (n - 1)) == 0;
}

// Without using pow(): 
bool forloop(const int n)
{
    for (int i = 0; i <= 30; i++)
    {
        int ans = 1;
        if (n == ans)
        {
            return true;
        }
        ans *= 2;
    }
    return false;
}

template <typename Func>
long long timeit_with_steady_clock(Func F, int it)
{
    auto start = std::chrono::steady_clock::now();
    for (int i = 0; i < it; i++)
    {
        F(i);
    }
    auto end = std::chrono::steady_clock::now();
    return std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
}

int main()
{
    const int it = 100000000;
    auto A = timeit_with_steady_clock(bitwise, it);
    auto B = timeit_with_steady_clock(forloop, it);
    std::cout << A << " ms vs. " << B << " ms - Ratio of forloop/bitwise is " << B / A << "\n";

    return 0;
}

Принты

280 ms vs. 4860 ms - Ratio of forloop/bitwise is 17

Комментарии:

• Разумно рассчитать время для первого кода будет практически невозможно без дополнительного контекста. Это займет всего несколько циклов. Например, загрузка значения n из памяти или даже просто кеша займет больше времени, чем фактическая операция. Значения, с которыми функция вызывается последовательно, могут привести к значительным различиям в прогнозировании ветвей, если в результирующей сборке есть ветвь. Второй код будет медленнее, но только потому, что текущие компиляторы, похоже, не выполняют ту конкретную замену цикла, которую я предложил. Это время может быть где-то в наносекундах, но не будет информативным. – пользователь17732522

• В общем, я думаю, единственное, что можно сказать OP, это то, что цикл будет значительно медленнее, если компилятор не сможет распознать, что его можно оптимизировать для нескольких неповторяемых инструкций, чего современные компиляторы, похоже, не делают. мог бы, но легко мог бы. – пользователь17732522

• Лучше избегатьhigh_resolution_clock и вместо этого использовать steady_clock. – опустошение кучи

Все распространенные двоичные арифметические и логические операции, за исключением деления, в современных компьютерных архитектурах занимают примерно одинаковое время (часто один цикл). Деление может быть в 10-20 раз медленнее.

Проблема здесь в хитроумном тестировании Leetcode. Второй метод требует гораздо больше работы! pow() имеет значительное время выполнения и называется 31x. Здесь нет никакой возможности победить.

Второй цикл можно было бы легко переписать, чтобы избежать вызова функции pow, но даже в этом случае он все равно будет выполнять примерно в 20 раз больше работы, чем первый метод.

bool better_forloop(const int n)
{
   int ans = 1;
   for (int i = 0; i <= 30; i++)
   {
      if (n == ans) return true;
      ans *= 2;
   }
   return false;
}

@TedLyngmo делает очень важное замечание, если операторы if и циклы for имеют неявную дополнительную стоимость для условной ветви, так что если вы можете вычислить результат true/false и вернуть его, то это всегда лучше.

Я изменил код, чтобы он возвращал int и превратился в классический C, чтобы в Godbolt это был минимальный код. Результаты интересны. GCC 14.1, безусловно, лучший из всех. Intel ICX в меньшей степени, а MSVC смешон даже при -O3.

Это результат ассемблера Godbolt из GCC 14.1, который оказался самой плотной и эффективной генерацией кода, которую я нашел. Первый метод 8 инструкций для любых n, второй метод 11 + n*(10+time for pow()) ~120 (мин) и максимум ~3000 (при n=30).

bitwise:
    xor     eax, eax
    test    edi, edi
    jle     .L1
    lea     eax, [rdi-1]
    test    eax, edi
    sete    al
    movzx   eax, al
.L1:
    ret
forloop:
    push    rbp
    mov     ebp, edi
    push    rbx
    xor     ebx, ebx
    sub     rsp, 8
    jmp     .L7
.L12:
    add     ebx, 1
    cmp     ebx, 31
    je      .L11
.L7:
    pxor    xmm1, xmm1
    movsd   xmm0, QWORD PTR .LC0[rip]
    cvtsi2sd        xmm1, ebx
    call    pow
    cvttsd2si       eax, xmm0
    cmp     eax, ebp
    jne     .L12
    add     rsp, 8
    mov     eax, 1
    pop     rbx
    pop     rbp
    ret
.L11:
    add     rsp, 8
    xor     eax, eax
    pop     rbx
    pop     rbp
    ret
.LC0:
    .long   0
    .long   1073741824

По быстрому и грязному предположению, каждая инструкция занимает в среднем около 1 цикла, за исключением call pow, что составляет около 100 машинных циклов. Pow приходится вычислить log 2, умножить на i, а затем вычислить экспоненту, что занимает много времени.