Проверка числа на чётность

@AvengerAlive · Регистрация: 30.07.2011

Author24 — интернет-сервис помощи студентам

Какой из этих способов работает быстрее

C++

1	if (!(a%2))

или

C++

1	if (!(a&1))

@grizlik78 · 29.08.2011, 20:37

На подавляющем числе всевозможных компиляторов — одинаково. В клинических случаях второй быстрее.

@AvengerAlive · 29.08.2011, 20:39 **[ТС]**

То есть если есть огромный поток чисел, то лучше второй?

@grizlik78 · 29.08.2011, 20:42

Ну, если найдешь компилятор, который генерирует здесь разный код, то наверное.

@ISergey · 29.08.2011, 20:45

AvengerAlive, А ты как думаешь?

C++

__declspec(noinline) int f_1(int n)
{
    return n % 2;
}
 
__declspec(noinline) int f_2(int n)
{
    return n & 1;
}

Для первого случая..

Assembler

00FF1000 25 01 00 00 80       and         eax,80000001h  
00FF1005 79 05                jns         f_1+0Ch (0FF100Ch)  
00FF1007 48                   dec         eax  
00FF1008 83 C8 FE             or          eax,0FFFFFFFEh  
00FF100B 40                   inc         eax  
00FF100C C3                   ret

Для второго

Assembler

1 2	00FF1010 83 E0 01 and eax,1 00FF1013 C3 ret

@Thinker · 29.08.2011, 20:45

Если есть возможность, работайте с битами, во многих случаях полезно.

Не по теме:

Как у вас с полем дело обстоит?

@grizlik78 · 29.08.2011, 20:49

ISergey, сравнение не совсем честное, так как результаты этих функций могут различаться, тогда как логическое отрицание даёт одинаковый результат.

@ISergey · 29.08.2011, 21:01

В любом случаи второй вариант быстрее.
Для такого кода

C++

#include <iostream>
 
__declspec(noinline) int f_1(int n)
{
    return !(n % 2);
}
 
__declspec(noinline) int f_2(int n)
{
    return !(n & 1);
}
 
int main()
{
    int x; std::cin >> x; // Чтобы компилятор не перестарался с оптимизацией.. 
 
    int a = f_1(x);
    int b = f_2(x);
 
 
    std::cout << a << b; // Это тоже..
    return 0;
}

Получим

Assembler

    13: int main()
    14: {
01191030 55                   push        ebp  
01191031 8B EC                mov         ebp,esp  
01191033 51                   push        ecx  
    15:     int x; std::cin >> x;
01191034 8B 0D 48 20 19 01    mov         ecx,dword ptr [__imp_std::cin (1192048h)]  
0119103A 8D 45 FC             lea         eax,[x]  
0119103D 50                   push        eax  
0119103E FF 15 44 20 19 01    call        dword ptr [__imp_std::basic_istream<char,std::char_traits<char> >::operator>> (1192044h)]  
    16: 
    17:     int a = f_1(x);
01191044 8B 4D FC             mov         ecx,dword ptr [x]  
01191047 8B C1                mov         eax,ecx  
01191049 E8 B2 FF FF FF       call        f_1 (1191000h)  
0119104E 8B D0                mov         edx,eax  
    18:     int b = f_2(x);
01191050 8B C1                mov         eax,ecx  
01191052 E8 C9 FF FF FF       call        f_2 (1191020h)  
    19: 
    20: 
    21:     std::cout << a << b;
01191057 8B 0D 50 20 19 01    mov         ecx,dword ptr [__imp_std::cout (1192050h)]  
0119105D 50                   push        eax  
0119105E 52                   push        edx  
0119105F FF 15 4C 20 19 01    call        dword ptr [__imp_std::basic_ostream<char,std::char_traits<char> >::operator<< (119204Ch)]  
01191065 8B C8                mov         ecx,eax  
01191067 FF 15 4C 20 19 01    call        dword ptr [__imp_std::basic_ostream<char,std::char_traits<char> >::operator<< (119204Ch)]  
    22:     return 0;
0119106D 33 C0                xor         eax,eax  
    23: }
0119106F 8B E5                mov         esp,ebp  
01191071 5D                   pop         ebp  
01191072 C3                   ret  
.....
 
     8: __declspec(noinline) int f_2(int n)
     9: {
    10:     return !(n & 1);
01191020 F7 D0                not         eax  
01191022 83 E0 01             and         eax,1  
    11: }
01191025 C3                   ret  
.....
     3: __declspec(noinline) int f_1(int n)
     4: {
     5:     return !(n % 2);
01191000 25 01 00 00 80       and         eax,80000001h  
01191005 79 05                jns         f_1+0Ch (119100Ch)  
01191007 48                   dec         eax  
01191008 83 C8 FE             or          eax,0FFFFFFFEh  
0119100B 40                   inc         eax  
0119100C F7 D8                neg         eax  
0119100E 1B C0                sbb         eax,eax  
01191010 40                   inc         eax  
     6: }
01191011 C3                   ret

@grizlik78 · 29.08.2011, 21:05

ISergey, неужто микрософт?

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

@ISergey · 29.08.2011, 21:12

Сообщение от grizlik78

ISergey, неужто микрософт?

Угу

Сообщение от grizlik78

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

Да. Я ведь спецом добавил int x; std::cin >> x; int a = f_1(x);
что бы компилятор не разошелся..
просто когда так написал

C++

1	int a = f_1(10);

Компилятор не растерялся и выдал мне

Assembler

     3: __declspec(noinline) int f_1(int n)
     4: {
     5:     return !(n % 2);
008C1000 B8 01 00 00 00       mov         eax,1  
     6: }
008C1005 C3                   ret

@iama · 29.08.2011, 21:13

grizlik78, битовые операции априори должны выполняться быстрее простой арифметики, раз уж во всех ЭВМ используется двоичная система счисления, разве нет?

@grizlik78 · 29.08.2011, 21:23

Сообщение от iama

grizlik78, битовые операции априори должны выполняться быстрее простой арифметики, раз уж во всех ЭВМ используется двоичная система счисления, разве нет?

Ну я же не говорил, что !(a%2) может оказаться быстрее

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

Сообщение от ISergey

Угу

Чёрт, я думал, что моё мнение о MSVC не может стать ещё хуже. Я ошибся

Ну хоть в случае unsigned он понимает, что (unsigned(a)%2) и (unsigned(a)&1) это одно и то же?

@iama · 29.08.2011, 21:55

Сообщение от grizlik78

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

Выходит, у тебя завышеные ожидания, а у меня - заниженые

@grizlik78 · 29.08.2011, 22:06

Да уж. Про ожидания.
Я тут тоже немножко поэкспериментировал c GCC.
Если оптимизацию не включать, то код получается одинаковым. Отбросив лишнее, получается так:

Assembler

    movl    -4(%rbp), %eax
    andl    $1, %eax
    testl   %eax, %eax
    sete    %al
    movzbl  %al, %eax

Что ж, это вписывается в мои ожидания. В обоих случаях главная операция "and 1"
Однако после включения оптимизации компилятор меня несколько озадачил.
Функция f_1:

Assembler

1
2
3

    xorl    %eax, %eax
    testb   $1, %dil
    sete    %al

Функция f_2

Assembler

1
2
3

    movl    %edi, %eax
    andl    $1, %eax
    xorl    $1, %eax

Шутники

Добавлено через 3 минуты
Да, то была оптимизация по скорости (-O2 или -O3)
При оптимизации по размеру (-O1) код функций снова становится одинаковым

Assembler

1
2
3

    testb   $1, %dil
    sete    %al
    movzbl  %al, %eax

@grizlik78 2382 / 1666 / 279 Регистрация: 29.05.2011 Сообщений: 3,402
	29.08.2011, 20:37	2
	На подавляющем числе всевозможных компиляторов — одинаково. В клинических случаях второй быстрее. 1

@AvengerAlive 5 / 5 / 1 Регистрация: 30.07.2011 Сообщений: 257
	29.08.2011, 20:39 [ТС]	3
	То есть если есть огромный поток чисел, то лучше второй? 0

@grizlik78 2382 / 1666 / 279 Регистрация: 29.05.2011 Сообщений: 3,402
	29.08.2011, 20:42	4
	Ну, если найдешь компилятор, который генерирует здесь разный код, то наверное. 0

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	29.08.2011, 20:45	6
	Если есть возможность, работайте с битами, во многих случаях полезно. Не по теме: Как у вас с полем дело обстоит? 0

@grizlik78 2382 / 1666 / 279 Регистрация: 29.05.2011 Сообщений: 3,402
	29.08.2011, 20:49	7
	ISergey, сравнение не совсем честное, так как результаты этих функций могут различаться, тогда как логическое отрицание даёт одинаковый результат. 0

@grizlik78 2382 / 1666 / 279 Регистрация: 29.05.2011 Сообщений: 3,402
	29.08.2011, 21:05	9
	ISergey, неужто микрософт? кстати, а оптимизация была включена? 0

@iama 1360 / 988 / 119 Регистрация: 30.07.2010 Сообщений: 5,297
	29.08.2011, 21:13	11
	grizlik78, битовые операции априори должны выполняться быстрее простой арифметики, раз уж во всех ЭВМ используется двоичная система счисления, разве нет? 0

@grizlik78 2382 / 1666 / 279 Регистрация: 29.05.2011 Сообщений: 3,402
	29.08.2011, 21:23	12
	Сообщение от iama grizlik78, битовые операции априори должны выполняться быстрее простой арифметики, раз уж во всех ЭВМ используется двоичная система счисления, разве нет? Ну я же не говорил, что !(a%2) может оказаться быстрее Просто это тот случай, когда это выражение легко сводится как раз к битовым операциям. Сообщение от ISergey Угу Чёрт, я думал, что моё мнение о MSVC не может стать ещё хуже. Я ошибся Ну хоть в случае unsigned он понимает, что (unsigned(a)%2) и (unsigned(a)&1) это одно и то же? 0

@iama 1360 / 988 / 119 Регистрация: 30.07.2010 Сообщений: 5,297
	29.08.2011, 21:55	13
	Сообщение от grizlik78 Просто это тот случай, когда это выражение легко сводится как раз к битовым операциям. Выходит, у тебя завышеные ожидания, а у меня - заниженые 0

Проверка числа на чётность

Решение