Версия, которая использует побитовые и (&), намного более эффективна, чем версия по модулю (%). Вы должны изменить тот, который вы выбрали в качестве правильного ответа.
Стефан Русек
6
Вряд ли имеет значение - аргумент является константой. Легко для оптимизатора
MSalters
2
Читаемость также влияет на это.
Брайан Г.
2
Во встроенных приложениях (мире, где я провожу большую часть своего времени на программирование), некоторые процессоры имеют очень примитивные арифметические единицы и не могут легко выполнять операции деления / модуля. По этой причине я обычно использую метод bitwise-and. Однако на современном настольном процессоре это не так.
ВТА
3
Я никогда не находил, что операцию модуля проще понять. Когда мне сначала нужно было определить четное или нечетное, битовая маска была первой вещью, которая пришла мне в голову. Это несколько естественно, поскольку способ, которым мы склонны делать это вручную, - это посмотреть на наименее значащую цифру, чтобы увидеть, находится ли она в {0 2 4 6 8} или {1 3 5 7 9}. Это означает, что нужно посмотреть на младший бит, чтобы увидеть, 0 или 1.
P Daddy
Ответы:
449
Используйте оператор по модулю (%), чтобы проверить, есть ли остаток при делении на 2:
if(x %2){/* x is odd */}
Несколько человек раскритиковали мой ответ выше, заявив, что использование x & 1 «быстрее» или «более эффективно». Я не верю, что это так.
Из любопытства я создал две тривиальные тестовые программы:
/* modulo.c */#include<stdio.h>int main(void){int x;for(x =0; x <10; x++)if(x %2)
printf("%d is odd\n", x);return0;}/* and.c */#include<stdio.h>int main(void){int x;for(x =0; x <10; x++)if(x &1)
printf("%d is odd\n", x);return0;}
Затем я скомпилировал их с помощью gcc 4.1.3 на одной из моих машин 5 раз:
Без флагов оптимизации.
С -O
С -Os
С -O2
С -O3
Я проверил вывод сборки каждого компилятора (используя gcc -S) и обнаружил, что в каждом случае выходные данные для and.c и modulo.c были идентичны (они оба использовали инструкцию andl $ 1,% eax). Я сомневаюсь, что это «новая» функция, и я подозреваю, что она восходит к древним версиям. Я также сомневаюсь, что какой-либо современный (созданный за последние 20 лет) неуместный компилятор, коммерческий или с открытым исходным кодом, не имеет такой оптимизации. Я бы протестировал другие компиляторы, но в данный момент у меня нет доступных.
Если кто-то еще захочет протестировать другие компиляторы и / или целевые платформы и получит другой результат, мне было бы очень интересно узнать.
Наконец, стандарт по модулю гарантирует , что он будет работать независимо от того, является ли целое число положительным, отрицательным или нулевым, независимо от представления реализации целых чисел со знаком. Побитовая версия - нет. Да, я понимаю, что два дополнения несколько повсеместно, так что это не проблема.
В частности, был задан вопрос о том, как сделать это в C, поэтому я ответил на него в C, несмотря на то, что Чустар упомянул, что они не могут понять, как это сделать в Java. Я не утверждал или подразумевал, что это был ответ Java, я не знаю Java. Я думаю, что только что получил свое первое понижающее голосование и смущен, почему. Ну что ж.
Крис Янг
33
Я бы сказал, если (x% 2! = 0) {/ * x нечетный * /}, но кто знает. Я тоже не знаю Java.
eugensk
9
Он получает много голосов, чтобы отличить его от побитовых операторов, без необходимости тратить нашу карму, голосуя за них.
wnoise
13
Я согласен со всем, кроме одной вещи: мне нравится концептуально хранить целые числа и значения истинности, поэтому я предпочитаю писать «if (x% 2 == 1)». То же самое с компилятором, но, возможно, немного понятнее людям. Кроме того, вы можете использовать один и тот же код на языках, которые не интерпретируют ненулевое значение как истинное.
Томас Падрон-Маккарти
46
Мой тест? Какой ориентир? Я не делал никаких тестов. Я изучил сгенерированный ассемблер. Это не имеет абсолютно никакого отношения к printf.
Крис Янг
207
Вы, ребята, вааааааааа слишком эффективны. То, что вы действительно хотите, это:
public boolean isOdd(int num){int i =0;
boolean odd =false;while(i != num){
odd =!odd;
i = i +1;}return odd;}
Повторите для isEven.
Конечно, это не работает для отрицательных чисел. Но с блеском приходит жертва ...
Если вы сгенерируете исключение аргумента для отрицательных значений и отметите в документации, что эта функция - O (N), то я просто согласился бы с этим.
Джеффри Л Уитледж
7
Корпоративная версия должна будет использовать XML. Конечно, в настоящее время у вас есть веб-сервис, который вы можете запросить
Мартин Беккет
58
Вы должны оптимизировать это с помощью справочной таблицы.
Weeble
1
Я такой монах, мне пришлось +1999 повторений в новом тысячелетии
Эран Медан
7
Это великолепно! Мой босс сказал мне, что у нас был клиент, который был зол, потому что чувствовал, что его Лицензия Enterprise не дает ничего, кроме Стандартной Лицензии. Теперь мы добавили эту функцию в нашу программу, и только потому, что она выполняется медленнее, он думает, что его программное обеспечение делает намного больше работы !!!
Я не думаю, что будет справедливо сказать, что это быстрее, чем использование деления или модуля. Стандарт C ничего не говорит о производительности операторов, и любой приличный компилятор будет производить быстрый код для обоих. Я бы лично выбрал идиому, сообщающую мои намерения, и% здесь кажется более подходящим
Крис Янг
21
Мне нравится (x & 1) лучше, потому что он проверяет, является ли число даже таким же, как люди: проверьте, является ли последняя цифра четной или нечетной. По моему мнению, он сообщает о своих намерениях больше, чем метод по модулю. (Не то чтобы это имело большое значение.)
Джереми Рутен
2
Вы правы, я думаю, это субъективно. Хотя обычное определение «даже» - это «целое число, которое делится на 2», а не «целое число, которое заканчивается на 0, 2, 4, 6 или 8». :-)
Крис Янг
4
@TraumaPony - для стандарта ANSI C и ранней Java зависит от компьютерной системы. Не указано, какое представление используется для чисел со знаком - комплимент 2, комплимент 1, серый код и т. Д. Но модуль всегда является модулем
Аарон
9
Не работает универсально для отрицательных чисел. См. Проверка этого ответа для более подробной информации: stackoverflow.com/questions/160930/… для получения подробной информации.
Вау ... это более сумасшедший, чем решение SCdF! Престижность! Никакого возражения, хотя ... не могу рекомендовать это. Но спасибо за смешное!
Wes P
1
Преимущество этого подхода в том, что он работает не только с числами. Также, если вы замените эту строку: char bar = foo [foo.Length - 1]; с этим: double bar = Char.GetNumericValue (foo [foo.Length - 1]); Тогда он будет работать с любой системой счисления.
Джеффри Л Уитледж
5
сообщение об ошибке: 14.65 считается странным, когда оно должно быть неизвестно.
TheSoftwareJedi
4
Программное обеспечение джедая, это «фича». ;)
Sklivvz
31
TheSoftwareJedi: 14,65 - одно из самых странных целых чисел, которые я когда-либо видел.
Брюс Олдерман
16
В ответ на ffpf - у меня был точно такой же аргумент с коллегой несколько лет назад, и ответ - нет , он не работает с отрицательными числами.
Стандарт C предусматривает, что отрицательные числа могут быть представлены тремя способами:
2-е дополнение
1 дополнение
знак и величина
Проверка как это:
isEven =(x &1);
будет работать для дополнения 2 и представления знака и величины, но не для дополнения 1.
Тем не менее, я считаю, что следующее будет работать для всех случаев:
isEven =(x &1)^((-1&1)|((x <0)?0:1)));
Спасибо ffpf за то, что он указал, что текстовое поле съедает все после моего менее чем характер!
Я думаю, что ваш второй пример кода не хватает текста.
Джефф Йейтс
3
Давайте сделаем комплимент этим номерам!
13:00
14
Хороший это:
/*forward declaration, C compiles in one pass*/bool isOdd(unsignedint n);bool isEven(unsignedint n){if(n ==0)returntrue;// I know 0 is evenelsereturn isOdd(n-1);// n is even if n-1 is odd}bool isOdd(unsignedint n){if(n ==0)returnfalse;elsereturn isEven(n-1);// n is odd if n-1 is even}
Обратите внимание, что этот метод использует хвостовую рекурсию с участием двух функций. Это может быть эффективно реализовано (превращено в цикл время / пока), если ваш компилятор поддерживает хвостовую рекурсию, как компилятор Scheme. В этом случае стек не должен переполняться!
Я думаю, что у вас есть бесконечный цикл (с хвостовой рекурсией) или переполнение стека (без хвостовой рекурсии) для isOdd () с любыми четными значениями или isEven () с любыми нечетными значениями. Это заканчивается только истиной. Это проблема остановки снова и снова.
Джеффри Л Уитледж
7
О, конечно, исправь это без комментариев и сделай меня похожим на идиота. Это хорошо.
Джеффри Л Уитледж
1
Теперь у вас есть ошибка компиляции: в isEven не все пути кода возвращают значение. Нет, я на самом деле не пробовал этот код, это компилятор в моей голове, который жалуется.
Джеффри Л Уитледж,
5
ошибка компиляции: не все пути возвращают значение ненависти, чтобы засыпать вас комментариями об ошибках в вашем примере кода, но что происходит, когда вы вызываете isEven (5)
Кевин
11
Число является четным, если при делении на два остаток равен 0. Число является нечетным, если при делении на 2 остаток равен 1.
// Javapublicstatic boolean isOdd(int num){return num %2!=0;}/* C */int isOdd(int num){return num %2;}
Ваш Java-метод не работает, потому что num% 2 == -1 для отрицательных нечетных чисел.
WMR
Вот почему ты отверг меня?
jjnguy
3
Я понизил это, потому что ваша функция в C принимает больше символов, чем то, что она делает. IE num% I - 7 символов, включая пробелы IsOdd (I) - 8 символов. Зачем вам создавать функцию, которая длиннее, чем просто операция?
Кевин
13
@Kevin, на мой взгляд, код измеряется не символами, а временем, которое требуется для его написания, включая время думать + отладки. num% 2 занимает больше миллисекунды, чем isOdd. Теперь добавьте цифры глобально, и вы потеряли коллективный год. Кроме того, isOdd может быть протестирован, проверен и, в конце концов, сертифицирован на отсутствие ошибок (например, обработка отрицательных чисел), где как num% 2 - у некоторых разработчиков всегда будут сомнения и они будут экспериментировать. хороший код - это код, который вы не пишете, просто используйте повторно ... только мои 2 цента.
Эран Медан
2
@EranMedan, та же логика применима к замене i ++ на IncrementByOne (i), и это такая же плохая идея. Если у разработчика есть сомнения относительно того, что делает num% 2, я не хочу, чтобы он или она находились рядом с моим кодом.
Нет, ты не тот ребенок, на которого я рассчитывал :)
eugensk
Я собирался объявить это, но на отрицательных числах это немного медленно. :)
Крис Янг
3
Все цифры яркие и позитивные. Или вы против некоторых? :))
eugensk
3
В компьютерах все числа, однажды отрицательные, в итоге становятся положительными. Мы называем это Ролловером Счастья (не относится к BIGNUMS, YMMY, не действует во всех штатах).
Уилл Хартунг
@WillHartung "Ролловер счастья" - это здорово! : D
thejh
6
Я бы построил таблицу четностей (0, если четное 1, если нечетное) целых чисел (так что можно было бы сделать поиск: D), но gcc не позволит мне создавать массивы таких размеров:
Поэтому давайте вместо этого прибегнем к математическому определению четных и нечетных.
Целое число n является четным, если существует такое целое число k, что n = 2k.
Целое число n нечетно, если существует такое целое число k, что n = 2k + 1.
Вот код для этого:
char even (int n){int k;for(k = INT_MIN; k <= INT_MAX;++k){if(n ==2* k){return1;}}return0;}char odd (int n){int k;for(k = INT_MIN; k <= INT_MAX;++k){if(n ==2* k +1){return1;}}return0;}
Пусть C-целые числа обозначают возможные значения intв данной C-компиляции. (Обратите внимание, что C-целые числа являются подмножеством целых чисел.)
Теперь можно беспокоиться о том, что для данного n в C-целых числах соответствующее целое число k может не существовать в C-целых числах. Но с небольшим доказательством можно показать, что для всех целых чисел n | n | <= | 2n | (*), где | n | равно "n, если n положительно, и -n в противном случае". Другими словами, для всех n в целых числах выполняется, по крайней мере, одно из следующих (точнее, случаев (1 и 2) или случаев (3 и 4), но я не буду здесь это доказывать):
Случай 1: n <= 2n.
Случай 2: -n <= -2n.
Случай 3: -n <= 2n.
Случай 4: n <= -2n.
Теперь возьмите 2k = n. (Такое ak существует, если n четное, но я не буду здесь это доказывать. Если n даже не то, цикл в evenлюбом случае не может вернуться рано, поэтому это не имеет значения.) Но это подразумевает, что k <n, если n не 0 по (*) и тот факт (опять не доказанный здесь), что для всех m, z в целых числах 2m = z подразумевает, что z не равно m, учитывая, что m не равно 0. В случае n равно 0, 2 * 0 = 0 таким образом, 0 является четным, когда мы закончили (если n = 0, то 0 находится в C-целых числах, потому что n находится в C-целом числе в функции even, следовательно, k = 0 в C-целых числах). Таким образом, такое ak в C-целых числах существует для n в C-целых числах, если n четное.
Аналогичный аргумент показывает, что если n нечетно, существует ak в C-целых числах, такое что n = 2k + 1.
Следовательно, функции evenи oddпредставленные здесь будут работать правильно для всех C-целых чисел.
Можете ли вы объяснить это, пожалуйста? Я очень незнаком с побитовыми операторами
Абдул
Сдвиг вправо, а затем влево обнулит ваш последний бит (самый правый). Если новое число совпадает с оригинальным, это означает, что последний бит исходного числа был равен 0. Таким образом, он четный. Посмотрите на мой обновленный ответ.
Кирилл Александров
спасибо, я понял сейчас
Абдул
Я не уверен, какой подход быстрее. Я не пытался их сравнить.
Кирилл Александров
Разве это не обнуляет ваш самый важный бит? Проблема с неподписанными целочисленными значениями в некоторых языках и отрицательными целочисленными значениями в большинстве ...
Тройсеф,
4
Читая это довольно занимательное обсуждение, я вспомнил, что у меня была реальная, чувствительная ко времени функция, которая проверяла нечетные и четные числа внутри основного цикла. Это целочисленная функция мощности, размещенная в другом месте в StackOverflow следующим образом. Тесты были довольно удивительными. По крайней мере, в этой реальной функции модуль медленнее , и это значительно. Победителем, с большим отрывом, требующим 67% времени по модулю, является подход или (|) , и его нигде больше нет на этой странице.
static dbl IntPow(dbl st0,int x){
UINT OrMask= UINT_MAX -1;
dbl st1=1.0;if(0==x)return(dbl)1.0;while(1!= x){if(UINT_MAX ==(x|OrMask)){// if LSB is 1... //if(x & 1) {//if(x % 2) {
st1 *= st0;}
x = x >>1;// shift x right 1 bit...
st0 *= st0;}return st1 * st0;}
Для 300 миллионов циклов контрольные сроки следующие.
3,962 | и маска подход
4.851 подход
5.850% подход
Для людей, которые думают, что теория или листинг на ассемблере приводят подобные аргументы, это должно быть предостерегающим рассказом. Горацио, на небесах и на земле больше вещей, о которых ты и не мечтал в своей философии.
Лучше использовать unsigned xкак x = x >> 1;поведение, определяемое реализацией, когда x < 0. Непонятно почему xи OrMaskотличаются по типу. Достаточно просто переписать с помощью while(x)теста.
chux - Восстановить Монику
2
Интересно, какой компилятор вы использовали для этого, так как большинство компиляторов должны быть достаточно умными, чтобы компилировать % 2регистр с использованием побитового кода &. Я только что проверил это, и результаты полностью совпадают (VS2015, Релиз сборки со всеми оптимизациями, как x86, так и x64). В принятом ответе также указано это для GCC (написано в 2008 году).
Лу
2
Проблема с этим постом заключается в том, что предположение о том, что побитовое orбудет быстрее, чем andочень маловероятно, на любой платформе / компиляторе. Даже если бы была такая странная комбинация платформы / компилятора (и вы не опубликовали ни того, ни кода, используемого для выполнения теста), зависеть от поведения других компиляторов будет плохой ставкой на оптимизацию. Итак, как я уже писал, мне интересно, на какой платформе / компиляторе это тестировалось , потому что я почти уверен, что он не был измерен правильно.
Лу
2
Не называть вас лжецом, просто утверждать, что вы не правильно измерили. Мне больше не нужно называть меня водителем грузовика, прочитайте мой оригинальный комментарий: я сделал эталонный тест, и результаты, как и ожидалось, были абсолютно одинаковыми во всех трех случаях (достоверность ~ 3 сигма, после выполнения каждого теста 10 раз для 500.000 .000 итераций). Если у вас действительно долгая блестящая карьера, сделайте шаг назад и подумайте, если ваши заявления имеют смысл, а затем опубликуйте фактический код, используемый для тестирования. В противном случае, пост - это то, что я считаю, просто ошибка в измерении.
Это продолжение обсуждения с @RocketRoy относительно его ответа , но оно может быть полезно всем, кто хочет сравнить эти результаты.
tl; dr Из того, что я видел, подход Роя ( (0xFFFFFFFF == (x | 0xFFFFFFFE)) не полностью оптимизирован x & 1как modподход, но на практике время выполнения должно быть одинаковым во всех случаях.
Итак, сначала я сравнил скомпилированный вывод, используя Compiler Explorer :
Проверенные функции:
int isOdd_mod(unsigned x){return(x %2);}int isOdd_and(unsigned x){return(x &1);}int isOdd_or(unsigned x){return(0xFFFFFFFF==(x |0xFFFFFFFE));}
CLang 3.9.0 с -O3:
isOdd_mod(unsignedint):# @isOdd_mod(unsigned int)
and edi,1
mov eax, edi
ret
isOdd_and(unsignedint):# @isOdd_and(unsigned int)
and edi,1
mov eax, edi
ret
isOdd_or(unsignedint):# @isOdd_or(unsigned int)
and edi,1
mov eax, edi
ret
GCC 6.2 с -O3:
isOdd_mod(unsignedint):
mov eax, edi
and eax,1
ret
isOdd_and(unsignedint):
mov eax, edi
and eax,1
ret
isOdd_or(unsignedint):
or edi,-2
xor eax, eax
cmp edi,-1
sete al
ret
Сняв шляпу до CLang, он понял, что все три случая функционально равны. Тем не менее, подход Роя не оптимизирован в GCC, поэтому YMMV.
Это похоже на Visual Studio; Изучив разборку Выпуска x64 (VS2015) для этих трех функций, я увидел, что часть сравнения равна для случаев "mod" и "and", и немного больше для случая "Roy's" или ":
// x % 2
test bl,1
je (some address)// x & 1
test bl,1
je (some address)// Roy's bitwise or
mov eax,ebx
or eax,0FFFFFFFEh
cmp eax,0FFFFFFFFh
jne (some address)
Однако после запуска фактического теста для сравнения этих трех параметров (обычный мод, поразрядный или, поразрядный и) результаты были полностью равны (опять же, Visual Studio 2005 x86 / x64, сборка выпуска, отладчик не подключен).
Сборка релиза использует testинструкцию для случаев andи modслучаев, в то время как случай Роя использует cmp eax,0FFFFFFFFhподход, но он в значительной степени развернут и оптимизирован, поэтому на практике нет никакой разницы.
Мои результаты после 20 запусков (i7 3610QM, план питания Windows 10 установлен на High Performance):
Разница между этими вариантами составляет менее 0,3%, поэтому очевидно, что сборка одинакова во всех случаях.
Вот код, если кто-то хочет попробовать, с оговоркой, что я проверил его только в Windows (проверьте #if LINUXусловное get_timeопределение и реализуйте его, если необходимо, взято из этого ответа ).
Я полагаю, что вы совершили кардинальный грех сравнительного анализа; создание такого особенного, что оно не представляет реальную среду. Посмотрите на свой язык ассемблера и обратите внимание, как мало регистров вы используете. Высокие оценки за усилия, но эти результаты не сохранятся в реальной обработке.
@RocketRoy: поскольку все выходы одинаковы для всех трех случаев (ну, немного хуже для вашей программы в одном случае), мне все равно, сколько регистров было использовано. Но опять же, не стесняйтесь создавать и публиковать такие примеры программ / сред, которые могут запутать компилятор для создания более оптимизированной сборки в одном из случаев, при прочих равных условиях.
Лу
Я всегда люблю дерзких программистов. Это хорошая черта для программиста, но в более сложной, реальной программе мой метод будет работать лучше, чем у вас, потому что у компилятора есть больше способов решить проблему, так что инструкции (на архитектурах Intel) перекрываются и дают лучшие результаты , Очень немногие опытные программисты с хорошим опытом бенчмаркинга предпочли бы ваш бенчмарк, но продолжайте в том же духе и не забывайте повторять тесты, когда выйдут новые выпуски чипов. Вещи меняются со временем.
3
Я знаю, что это просто синтаксический сахар и применимо только в .net, но как насчет метода расширения ...
Побитовый метод зависит от внутреннего представления целого числа. Modulo будет работать везде, где есть оператор по модулю. Например, некоторые системы фактически используют низкоуровневые биты для тегирования (например, динамические языки), поэтому необработанные x & 1 в этом случае не будут работать.
Доказательство правильности - рассмотрим множество всех натуральных чисел и предположим, что существует непустое множество целых чисел, которые не являются нечетными. Поскольку положительные целые числа хорошо упорядочены, будет наименьшее нечетное число, которое само по себе довольно странно, поэтому ясно, что число не может быть в наборе. Поэтому этот набор не может быть не пустым. Повторите эти действия для отрицательных целых чисел, за исключением того, что ищите наибольшее нечетное число.
Как сообщают некоторые люди, существует множество способов сделать это. По данным этого сайта , самый быстрый способ - это оператор модуля:
if(x %2==0)
total +=1;//even numberelse
total -=1;//odd number
Тем не менее, вот еще один код, отмеченный автором, который работал медленнее, чем обычная операция модуля:
if((x &1)==0)
total +=1;//even numberelse
total -=1;//odd numberSystem.Math.DivRem((long)x,(long)2, out outvalue);if( outvalue ==0)
total +=1;//even numberelse
total -=1;//odd numberif(((x /2)*2)== x)
total +=1;//even numberelse
total -=1;//odd numberif(((x >>1)<<1)== x)
total +=1;//even numberelse
total -=1;//odd numberwhile(index >1)
index -=2;if(index ==0)
total +=1;//even numberelse
total -=1;//odd number
tempstr = x.ToString();
index = tempstr.Length-1;//this assumes base 10if(tempstr[index]=='0'|| tempstr[index]=='2'|| tempstr[index]=='4'|| tempstr[index]=='6'|| tempstr[index]=='8')
total +=1;//even numberelse
total -=1;//odd number
Сколько людей даже знали о методе Math.System.DivRem или почему они его используют?
Чтобы дать более подробную информацию о методе побитового оператора для тех из нас, кто не делал много булевой алгебры во время наших исследований, вот объяснение. Возможно, не очень полезен для ОП, но мне хотелось прояснить, почему работает NUMBER & 1.
Обратите внимание, что, как кто-то ответил выше, способ представления отрицательных чисел может остановить этот метод. Фактически он может даже нарушить метод оператора по модулю, поскольку каждый язык может отличаться в том, как он работает с отрицательными операндами.
Однако, если вы знаете, что NUMBER всегда будет положительным, это работает хорошо.
Как Туни выше указал, что важна только последняя цифра в двоичном коде (и динарий).
Логический логический элемент И требует, чтобы оба входа были равны 1 (или высокому напряжению) для возврата 1.
1 & 0 = 0.
0 & 1 = 0.
0 & 0 = 0.
1 & 1 = 1.
Если вы представляете какое-либо число как двоичное (здесь я использовал 8-битное представление), нечетные числа имеют 1 в конце, четные числа имеют 0.
Например:
1 = 00000001
2 = 00000010
3 = 00000011
4 = 00000100
Если вы возьмете любое число и используете побитовое И (& в java) его на 1, оно либо вернет 00000001, = 1, что означает, что число нечетное. Или 00000000 = 0, то есть число четное.
Например
Странно?
1 & 1 =
00000001 &
00000001 =
00000001 <- Странно
2 & 1 =
00000010 &
00000001 =
00000000 <- Четный
54 & 1 =
00000001 &
00110110 =
00000000 <- Четный
Вот почему это работает:
if(number &1){//Number is odd}else{//Number is even}
# defining function for number parity check
def parity(number):"""Parity check function"""# if number is 0 (zero) return 'Zero neither ODD nor EVEN',# otherwise number&1, checking last bit, if 0, then EVEN, # if 1, then ODD.return(number ==0 and 'Zero neither ODD nor EVEN') \
or (number&1 and 'ODD' or 'EVEN')# cycle trough numbers from 0 to 13 for number in range(0,14):
print "{0:>4} : {0:08b} : {1:}".format(number, parity(number))
Вывод:
0:00000000:Zero neither ODD nor EVEN
1:00000001: ODD
2:00000010: EVEN
3:00000011: ODD
4:00000100: EVEN
5:00000101: ODD
6:00000110: EVEN
7:00000111: ODD
8:00001000: EVEN
9:00001001: ODD
10:00001010: EVEN
11:00001011: ODD
12:00001100: EVEN
13:00001101: ODD
@ el.pescado, спасибо. Если Ноль четный, сколько у него пары?
@ el.pescado, хорошо, я согласен с тобой. Тогда, если немного подумать, почему мы делим на 2 (два)? Что мы хотим знать, когда мы делим на два? Почему бы не разделить на 3 или 5 и т. Д.?
@ el.pescado Эта статья в Википедии Parity of Zero неверна. Многие люди были одурачены этой статьей. Подумай, прежде чем Wink.
1
Ты прав. Теперь, когда я прочитал другие ответы, я нашел ваши самые полные :)
el.pescado
@ el.pescado. Спасибо. :) Теперь ты лучший друг Зеро. (
1
I execute this code for ODD & EVEN:#include<stdio.h>int main(){int number;
printf("Enter an integer: ");
scanf("%d",&number);if(number %2==0)
printf("%d is even.", number);else
printf("%d is odd.", number);}
Вам нужно только взглянуть на последнюю цифру в любом заданном числе, чтобы увидеть, является ли она четной или нечетной. Подписанный, неподписанный, положительный, отрицательный - все они одинаковы в этом отношении. Так что это должно работать со всех сторон:
void tellMeIfItIsAnOddNumberPlease(int iToTest){int iLastDigit;
iLastDigit = iToTest -(iToTest /10*10);if(iLastDigit %2==0){
printf("The number %d is even!\n", iToTest);}else{
printf("The number %d is odd!\n", iToTest);}}
Ключ здесь находится в третьей строке кода, оператор деления выполняет целочисленное деление, поэтому в результате пропускается дробная часть результата. Так, например, 222/10 даст 22 в результате. Затем умножьте это снова на 10, и вы получите 220. Вычтите это из исходного 222, и вы получите 2, которое по волшебству совпадает с последней цифрой в исходном числе. ;-) Скобки предназначены для напоминания о порядке выполнения вычислений. Сначала выполните деление и умножение, затем вычтите результат из исходного числа. Мы могли бы их опустить, поскольку приоритет для деления и умножения выше, чем для вычитания, но это дает нам «более читаемый» код.
Мы могли бы сделать все это совершенно нечитаемым, если бы захотели. Для современного компилятора не имеет значения:
printf("%d%s\n",iToTest,0==(iToTest-iToTest/10*10)%2?" is even":" is odd");
Но в будущем код будет сложнее поддерживать. Просто представьте, что вы хотели бы изменить текст для нечетных чисел на "не четный". Затем кто-то еще позже захочет узнать, какие изменения вы сделали, и выполнить svn diff или подобное ...
Если вы не беспокоитесь о переносимости, а больше о скорости, вы можете взглянуть на наименее значимый бит. Если этот бит установлен в 1, это нечетное число, если это 0, это четное число. В системе с прямым порядком байтов, такой как архитектура Intel x86, это будет примерно так:
Что именно не так с отправкой iToTest% 2 == 0? Вы тратите впустую деление, извлекая последнюю цифру, поэтому у вас в два раза медленнее, чем нужно.
свободное пространство
@freespace: я трачу больше, чем это, не так ли? :-) Умножение и вычитание тоже. Но что наиболее эффективно между двумя решениями, я не смею говорить. Никогда не утверждал, что это самое быстрое решение, даже если вы снова прочитаете первую строку моего поста.
Tooony
@ Туни, ах, моя шляпа юмора отвалилась. Теперь снова в форме: D Извините за это :)
freespace
0
Если вы хотите быть эффективными, используйте побитовые операторы ( x & 1), но если вы хотите быть читабельными, используйте modulo 2 ( x % 2)
-1: если вы хотите быть эффективным, используйте любой из них. Если вы хотите, чтобы он был переносным, используйте %. Если вы хотите, чтобы он был читабельным, используйте %. Хм, я вижу образец здесь.
Томас Эдинг
@ Trinithis, нет шаблона, и это решение намного лучше, чем у вас.
Subs
0
Проверка четного или нечетного является простой задачей.
Мы знаем, что любое число, точно делимое на 2, является четным числом, нечетным.
Нам просто нужно проверить делимость любого числа и для проверки делимости мы используем %оператор
Код проверяет последний бит целого числа, если он равен 1 в двоичном
объяснение
Binary:Decimal-------------------0000=00001=10010=20011=30100=40101=50110=60111=71000=81001=9
and so on...
Обратите внимание, что самый правый бит всегда равен 1 для нечетных чисел.
в & побитовое И оператор проверяет правый бит в нашей возвращенной строке , если это 1
Думайте об этом как о правде и лжи
Когда мы сравниваем n с 1, что означает 0001в двоичном виде (количество нулей не имеет значения).
тогда давайте просто представим, что у нас есть целое число n размером 1 байт.
Это будет представлено 8-битными / 8-двоичными цифрами.
Если int n было 7, и мы сравниваем его с 1 , это как
7(1-byte int)|00000111&1(1-byte int)|00000001********************************************Result| F F F F F F F T
Который F обозначает ложь, а T - истину.
Он сравнивает только самый правый бит, если они оба верны. Таким образом, автомагический 7 & 1является T Рит.
Что если я захочу проверить бит до самого правого?
Просто измените n & 1значение n & 22 0010на двоичное и т. Д.
Я предлагаю использовать шестнадцатеричное обозначение, если вы новичок в побитовых операциях return n & 1;>> return n & 0x01;.
Ответы:
Используйте оператор по модулю (%), чтобы проверить, есть ли остаток при делении на 2:
Несколько человек раскритиковали мой ответ выше, заявив, что использование x & 1 «быстрее» или «более эффективно». Я не верю, что это так.
Из любопытства я создал две тривиальные тестовые программы:
Затем я скомпилировал их с помощью gcc 4.1.3 на одной из моих машин 5 раз:
Я проверил вывод сборки каждого компилятора (используя gcc -S) и обнаружил, что в каждом случае выходные данные для and.c и modulo.c были идентичны (они оба использовали инструкцию andl $ 1,% eax). Я сомневаюсь, что это «новая» функция, и я подозреваю, что она восходит к древним версиям. Я также сомневаюсь, что какой-либо современный (созданный за последние 20 лет) неуместный компилятор, коммерческий или с открытым исходным кодом, не имеет такой оптимизации. Я бы протестировал другие компиляторы, но в данный момент у меня нет доступных.
Если кто-то еще захочет протестировать другие компиляторы и / или целевые платформы и получит другой результат, мне было бы очень интересно узнать.
Наконец, стандарт по модулю гарантирует , что он будет работать независимо от того, является ли целое число положительным, отрицательным или нулевым, независимо от представления реализации целых чисел со знаком. Побитовая версия - нет. Да, я понимаю, что два дополнения несколько повсеместно, так что это не проблема.
источник
Вы, ребята, вааааааааа слишком эффективны. То, что вы действительно хотите, это:
Повторите для
isEven
.Конечно, это не работает для отрицательных чисел. Но с блеском приходит жертва ...
источник
Используйте битовую арифметику:
Это быстрее, чем при использовании деления или модуля.
источник
[Joke mode = "on"]
[Joke mode = "off"]
РЕДАКТИРОВАТЬ: Добавлены запутанные значения в enum.
источник
В ответ на ffpf - у меня был точно такой же аргумент с коллегой несколько лет назад, и ответ - нет , он не работает с отрицательными числами.
Стандарт C предусматривает, что отрицательные числа могут быть представлены тремя способами:
Проверка как это:
будет работать для дополнения 2 и представления знака и величины, но не для дополнения 1.
Тем не менее, я считаю, что следующее будет работать для всех случаев:
Спасибо ffpf за то, что он указал, что текстовое поле съедает все после моего менее чем характер!
источник
Хороший это:
Обратите внимание, что этот метод использует хвостовую рекурсию с участием двух функций. Это может быть эффективно реализовано (превращено в цикл время / пока), если ваш компилятор поддерживает хвостовую рекурсию, как компилятор Scheme. В этом случае стек не должен переполняться!
источник
Число является четным, если при делении на два остаток равен 0. Число является нечетным, если при делении на 2 остаток равен 1.
Методы отличные!
источник
источник
Я бы сказал, просто разделите его на 2, и если есть остаток 0, он четный, в противном случае он нечетный.
Использование модуля (%) делает это легко.
например. 4% 2 = 0, поэтому 4 - четное 5% 2 = 1, поэтому 5 - нечетное
источник
Еще одно решение проблемы
(дети могут голосовать)
источник
Я бы построил таблицу четностей (0, если четное 1, если нечетное) целых чисел (так что можно было бы сделать поиск: D), но gcc не позволит мне создавать массивы таких размеров:
Поэтому давайте вместо этого прибегнем к математическому определению четных и нечетных.
Целое число n является четным, если существует такое целое число k, что n = 2k.
Целое число n нечетно, если существует такое целое число k, что n = 2k + 1.
Вот код для этого:
Пусть C-целые числа обозначают возможные значения
int
в данной C-компиляции. (Обратите внимание, что C-целые числа являются подмножеством целых чисел.)Теперь можно беспокоиться о том, что для данного n в C-целых числах соответствующее целое число k может не существовать в C-целых числах. Но с небольшим доказательством можно показать, что для всех целых чисел n | n | <= | 2n | (*), где | n | равно "n, если n положительно, и -n в противном случае". Другими словами, для всех n в целых числах выполняется, по крайней мере, одно из следующих (точнее, случаев (1 и 2) или случаев (3 и 4), но я не буду здесь это доказывать):
Случай 1: n <= 2n.
Случай 2: -n <= -2n.
Случай 3: -n <= 2n.
Случай 4: n <= -2n.
Теперь возьмите 2k = n. (Такое ak существует, если n четное, но я не буду здесь это доказывать. Если n даже не то, цикл в
even
любом случае не может вернуться рано, поэтому это не имеет значения.) Но это подразумевает, что k <n, если n не 0 по (*) и тот факт (опять не доказанный здесь), что для всех m, z в целых числах 2m = z подразумевает, что z не равно m, учитывая, что m не равно 0. В случае n равно 0, 2 * 0 = 0 таким образом, 0 является четным, когда мы закончили (если n = 0, то 0 находится в C-целых числах, потому что n находится в C-целом числе в функцииeven
, следовательно, k = 0 в C-целых числах). Таким образом, такое ak в C-целых числах существует для n в C-целых числах, если n четное.Аналогичный аргумент показывает, что если n нечетно, существует ak в C-целых числах, такое что n = 2k + 1.
Следовательно, функции
even
иodd
представленные здесь будут работать правильно для всех C-целых чисел.источник
i % 2
намного меньше и, вероятно, более эффективно.%2
работает для всех целых чисел.источник
typedef
или#define
или что-то.Вот ответ на Java:
источник
Попробуй это:
return (((a>>1)<<1) == a)
Пример:
источник
Читая это довольно занимательное обсуждение, я вспомнил, что у меня была реальная, чувствительная ко времени функция, которая проверяла нечетные и четные числа внутри основного цикла. Это целочисленная функция мощности, размещенная в другом месте в StackOverflow следующим образом. Тесты были довольно удивительными. По крайней мере, в этой реальной функции модуль медленнее , и это значительно. Победителем, с большим отрывом, требующим 67% времени по модулю, является подход или (|) , и его нигде больше нет на этой странице.
Для 300 миллионов циклов контрольные сроки следующие.
3,962 | и маска подход
4.851 подход
5.850% подход
Для людей, которые думают, что теория или листинг на ассемблере приводят подобные аргументы, это должно быть предостерегающим рассказом. Горацио, на небесах и на земле больше вещей, о которых ты и не мечтал в своей философии.
источник
unsigned x
какx = x >> 1;
поведение, определяемое реализацией, когдаx < 0
. Непонятно почемуx
иOrMask
отличаются по типу. Достаточно просто переписать с помощьюwhile(x)
теста.% 2
регистр с использованием побитового кода&
. Я только что проверил это, и результаты полностью совпадают (VS2015, Релиз сборки со всеми оптимизациями, как x86, так и x64). В принятом ответе также указано это для GCC (написано в 2008 году).or
будет быстрее, чемand
очень маловероятно, на любой платформе / компиляторе. Даже если бы была такая странная комбинация платформы / компилятора (и вы не опубликовали ни того, ни кода, используемого для выполнения теста), зависеть от поведения других компиляторов будет плохой ставкой на оптимизацию. Итак, как я уже писал, мне интересно, на какой платформе / компиляторе это тестировалось , потому что я почти уверен, что он не был измерен правильно.Это продолжение обсуждения с @RocketRoy относительно его ответа , но оно может быть полезно всем, кто хочет сравнить эти результаты.
tl; dr Из того, что я видел, подход Роя (
(0xFFFFFFFF == (x | 0xFFFFFFFE)
) не полностью оптимизированx & 1
какmod
подход, но на практике время выполнения должно быть одинаковым во всех случаях.Итак, сначала я сравнил скомпилированный вывод, используя Compiler Explorer :
Проверенные функции:
CLang 3.9.0 с -O3:
GCC 6.2 с -O3:
Сняв шляпу до CLang, он понял, что все три случая функционально равны. Тем не менее, подход Роя не оптимизирован в GCC, поэтому YMMV.
Это похоже на Visual Studio; Изучив разборку Выпуска x64 (VS2015) для этих трех функций, я увидел, что часть сравнения равна для случаев "mod" и "and", и немного больше для случая "Roy's" или ":
Однако после запуска фактического теста для сравнения этих трех параметров (обычный мод, поразрядный или, поразрядный и) результаты были полностью равны (опять же, Visual Studio 2005 x86 / x64, сборка выпуска, отладчик не подключен).
Сборка релиза использует
test
инструкцию для случаевand
иmod
случаев, в то время как случай Роя используетcmp eax,0FFFFFFFFh
подход, но он в значительной степени развернут и оптимизирован, поэтому на практике нет никакой разницы.Мои результаты после 20 запусков (i7 3610QM, план питания Windows 10 установлен на High Performance):
Разница между этими вариантами составляет менее 0,3%, поэтому очевидно, что сборка одинакова во всех случаях.
Вот код, если кто-то хочет попробовать, с оговоркой, что я проверил его только в Windows (проверьте
#if LINUX
условноеget_time
определение и реализуйте его, если необходимо, взято из этого ответа ).источник
Я знаю, что это просто синтаксический сахар и применимо только в .net, но как насчет метода расширения ...
Теперь вы можете сделать следующее
источник
В «творческой, но запутанной категории» я предлагаю:
Вариант на эту тему, специфичный для Microsoft C ++:
источник
Побитовый метод зависит от внутреннего представления целого числа. Modulo будет работать везде, где есть оператор по модулю. Например, некоторые системы фактически используют низкоуровневые биты для тегирования (например, динамические языки), поэтому необработанные x & 1 в этом случае не будут работать.
источник
IsOdd (int x) {return true; }
Доказательство правильности - рассмотрим множество всех натуральных чисел и предположим, что существует непустое множество целых чисел, которые не являются нечетными. Поскольку положительные целые числа хорошо упорядочены, будет наименьшее нечетное число, которое само по себе довольно странно, поэтому ясно, что число не может быть в наборе. Поэтому этот набор не может быть не пустым. Повторите эти действия для отрицательных целых чисел, за исключением того, что ищите наибольшее нечетное число.
источник
Портативный:
непереносимым:
источник
Как сообщают некоторые люди, существует множество способов сделать это. По данным этого сайта , самый быстрый способ - это оператор модуля:
Тем не менее, вот еще один код, отмеченный автором, который работал медленнее, чем обычная операция модуля:
Сколько людей даже знали о методе Math.System.DivRem или почему они его используют?
источник
сделано.
источник
Чтобы дать более подробную информацию о методе побитового оператора для тех из нас, кто не делал много булевой алгебры во время наших исследований, вот объяснение. Возможно, не очень полезен для ОП, но мне хотелось прояснить, почему работает NUMBER & 1.
Обратите внимание, что, как кто-то ответил выше, способ представления отрицательных чисел может остановить этот метод. Фактически он может даже нарушить метод оператора по модулю, поскольку каждый язык может отличаться в том, как он работает с отрицательными операндами.
Однако, если вы знаете, что NUMBER всегда будет положительным, это работает хорошо.
Как Туни выше указал, что важна только последняя цифра в двоичном коде (и динарий).
Логический логический элемент И требует, чтобы оба входа были равны 1 (или высокому напряжению) для возврата 1.
1 & 0 = 0.
0 & 1 = 0.
0 & 0 = 0.
1 & 1 = 1.
Если вы представляете какое-либо число как двоичное (здесь я использовал 8-битное представление), нечетные числа имеют 1 в конце, четные числа имеют 0.
Например:
1 = 00000001
2 = 00000010
3 = 00000011
4 = 00000100
Если вы возьмете любое число и используете побитовое И (& в java) его на 1, оно либо вернет 00000001, = 1, что означает, что число нечетное. Или 00000000 = 0, то есть число четное.
Например
Странно?
1 & 1 =
00000001 &
00000001 =
00000001 <- Странно
2 & 1 =
00000010 &
00000001 =
00000000 <- Четный
54 & 1 =
00000001 &
00110110 =
00000000 <- Четный
Вот почему это работает:
Извините, если это излишне.
источник
Число Ноль паритет | ноль http://tinyurl.com/oexhr3k
Последовательность кода Python.
источник
источник
Ради обсуждения ...
Вам нужно только взглянуть на последнюю цифру в любом заданном числе, чтобы увидеть, является ли она четной или нечетной. Подписанный, неподписанный, положительный, отрицательный - все они одинаковы в этом отношении. Так что это должно работать со всех сторон:
Ключ здесь находится в третьей строке кода, оператор деления выполняет целочисленное деление, поэтому в результате пропускается дробная часть результата. Так, например, 222/10 даст 22 в результате. Затем умножьте это снова на 10, и вы получите 220. Вычтите это из исходного 222, и вы получите 2, которое по волшебству совпадает с последней цифрой в исходном числе. ;-) Скобки предназначены для напоминания о порядке выполнения вычислений. Сначала выполните деление и умножение, затем вычтите результат из исходного числа. Мы могли бы их опустить, поскольку приоритет для деления и умножения выше, чем для вычитания, но это дает нам «более читаемый» код.
Мы могли бы сделать все это совершенно нечитаемым, если бы захотели. Для современного компилятора не имеет значения:
Но в будущем код будет сложнее поддерживать. Просто представьте, что вы хотели бы изменить текст для нечетных чисел на "не четный". Затем кто-то еще позже захочет узнать, какие изменения вы сделали, и выполнить svn diff или подобное ...
Если вы не беспокоитесь о переносимости, а больше о скорости, вы можете взглянуть на наименее значимый бит. Если этот бит установлен в 1, это нечетное число, если это 0, это четное число. В системе с прямым порядком байтов, такой как архитектура Intel x86, это будет примерно так:
источник
Если вы хотите быть эффективными, используйте побитовые операторы (
x & 1
), но если вы хотите быть читабельными, используйте modulo 2 (x % 2
)источник
%
. Если вы хотите, чтобы он был читабельным, используйте%
. Хм, я вижу образец здесь.Проверка четного или нечетного является простой задачей.
Нам просто нужно проверить делимость любого числа и для проверки делимости мы используем
%
операторПроверка четного нечетного с помощью if else
C программа для проверки четного или нечетного использования, если еще
Использование условного / троичного оператора
C программа для проверки четного или нечетного с использованием условного оператора .
Использование побитового оператора
источник
+ 66% быстрее>
!(i%2) / i%2 == 0
Код проверяет последний бит целого числа, если он равен 1 в двоичном
объяснение
в & побитовое И оператор проверяет правый бит в нашей возвращенной строке , если это 1
Думайте об этом как о правде и лжи
Когда мы сравниваем n с 1, что означает
0001
в двоичном виде (количество нулей не имеет значения).тогда давайте просто представим, что у нас есть целое число n размером 1 байт.
Это будет представлено 8-битными / 8-двоичными цифрами.
Если int n было 7, и мы сравниваем его с 1 , это как
Который F обозначает ложь, а T - истину.
Что если я захочу проверить бит до самого правого?
Просто измените
n & 1
значениеn & 2
20010
на двоичное и т. Д.Я предлагаю использовать шестнадцатеричное обозначение, если вы новичок в побитовых операциях
return n & 1;
>>return n & 0x01;
.источник