如何检查给定数字在C中是偶数还是奇数?
31 回答
使用模 (%) 运算符检查除以 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);
return 0;
}
/* 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);
return 0;
}
然后我在我的一台机器上用 gcc 4.1.3 编译了 5 次:
- 没有优化标志。
- 带-O
- 带 -Os
- 与 -O2
- 与-O3
我检查了每次编译的汇编输出(使用 gcc -S),发现在每种情况下,and.c 和 modulo.c 的输出都是相同的(它们都使用了 andl $1, %eax 指令)。我怀疑这是一个“新”功能,我怀疑它可以追溯到古代版本。我也怀疑任何现代(过去 20 年制造的)非神秘编译器,无论是商业的还是开源的,都缺乏这种优化。我会在其他编译器上进行测试,但目前我没有任何可用的。
如果其他人愿意测试其他编译器和/或平台目标,并得到不同的结果,我很想知道。
最后,标准保证模版本无论整数是正数、负数还是零都可以工作,而不管实现对有符号整数的表示。按位与版本不是。是的,我意识到二进制补码无处不在,所以这不是一个真正的问题。
你们太有效率了。你真正想要的是:
public boolean isOdd(int num) {
int i = 0;
boolean odd = false;
while (i != num) {
odd = !odd;
i = i + 1;
}
return odd;
}
重复isEven
。
当然,这不适用于负数。但伴随着辉煌而来的是牺牲……
使用位算术:
if((x & 1) == 0)
printf("EVEN!\n");
else
printf("ODD!\n");
这比使用除法或模数要快。
[笑话模式=“开”]
public enum Evenness
{
Unknown = 0,
Even = 1,
Odd = 2
}
public static Evenness AnalyzeEvenness(object o)
{
if (o == null)
return Evenness.Unknown;
string foo = o.ToString();
if (String.IsNullOrEmpty(foo))
return Evenness.Unknown;
char bar = foo[foo.Length - 1];
switch (bar)
{
case '0':
case '2':
case '4':
case '6':
case '8':
return Evenness.Even;
case '1':
case '3':
case '5':
case '7':
case '9':
return Evenness.Odd;
default:
return Evenness.Unknown;
}
}
[笑话模式=“关闭”]
编辑:向枚举添加了令人困惑的值。
作为对ffpf的回应- 几年前我和一位同事有完全相同的论点,答案是否定的,它不适用于负数。
C标准规定负数可以用3种方式表示:
- 2 的补码
- 1 的补码
- 符号和大小
像这样检查:
isEven = (x & 1);
将适用于 2 的补码以及符号和幅度表示,但不适用于 1 的补码。
但是,我相信以下内容适用于所有情况:
isEven = (x & 1) ^ ((-1 & 1) | ((x < 0) ? 0 : 1)));
感谢 ffpf 指出文本框在我的小于字符之后吃掉了所有东西!
一个不错的是:
/*forward declaration, C compiles in one pass*/
bool isOdd(unsigned int n);
bool isEven(unsigned int n)
{
if (n == 0)
return true ; // I know 0 is even
else
return isOdd(n-1) ; // n is even if n-1 is odd
}
bool isOdd(unsigned int n)
{
if (n == 0)
return false ;
else
return isEven(n-1) ; // n is odd if n-1 is even
}
请注意,此方法使用涉及两个函数的尾递归。如果你的编译器像 Scheme 编译器一样支持尾递归,它可以有效地实现(变成一个 while/until 循环)。在这种情况下,堆栈不应该溢出!
一个数是偶数,如果除以二,余数是 0。一个数是奇数,如果,除以 2,余数是 1。
// Java
public static boolean isOdd(int num){
return num % 2 != 0;
}
/* C */
int isOdd(int num){
return num % 2;
}
方法很棒!
i % 2 == 0
我会说只需将其除以 2,如果余数为 0,则为偶数,否则为奇数。
使用模数 (%) 使这很容易。
例如。4 % 2 = 0 因此 4 是偶数 5 % 2 = 1 因此 5 是奇数
解决问题的另一种方法
(欢迎孩子们投票)
bool isEven(unsigned int x)
{
unsigned int half1 = 0, half2 = 0;
while (x)
{
if (x) { half1++; x--; }
if (x) { half2++; x--; }
}
return half1 == half2;
}
我会建立一个整数的奇偶校验表(如果是奇偶校验则为 0)(因此可以进行查找:D),但 gcc 不会让我制作这种大小的数组:
typedef unsigned int uint;
char parity_uint [UINT_MAX];
char parity_sint_shifted [((uint) INT_MAX) + ((uint) abs (INT_MIN))];
char* parity_sint = parity_sint_shifted - INT_MIN;
void build_parity_tables () {
char parity = 0;
unsigned int ui;
for (ui = 1; ui <= UINT_MAX; ++ui) {
parity_uint [ui - 1] = parity;
parity = !parity;
}
parity = 0;
int si;
for (si = 1; si <= INT_MAX; ++si) {
parity_sint [si - 1] = parity;
parity = !parity;
}
parity = 1;
for (si = -1; si >= INT_MIN; --si) {
parity_sint [si] = parity;
parity = !parity;
}
}
char uparity (unsigned int n) {
if (n == 0) {
return 0;
}
return parity_uint [n - 1];
}
char sparity (int n) {
if (n == 0) {
return 0;
}
if (n < 0) {
++n;
}
return parity_sint [n - 1];
}
因此,让我们改用偶数和奇数的数学定义。
一个整数 n 是即使存在一个整数 k 使得 n = 2k。
如果存在整数 k 使得 n = 2k + 1,则整数 n 是奇数。
这是它的代码:
char even (int n) {
int k;
for (k = INT_MIN; k <= INT_MAX; ++k) {
if (n == 2 * k) {
return 1;
}
}
return 0;
}
char odd (int n) {
int k;
for (k = INT_MIN; k <= INT_MAX; ++k) {
if (n == 2 * k + 1) {
return 1;
}
}
return 0;
}
int
让 C 整数表示给定 C 编译中的可能值。(请注意,C 整数是整数的子集。)
现在有人可能会担心,对于给定的 C 整数中的 n,对应的整数 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。(如果 n 是偶数,这样的 ak 确实存在,但我不会在这里证明它。如果 n 不是偶数,那么循环even
无论如何都无法提前返回,所以没关系。)但这意味着 k < n if n不是 0 (*) 和事实(这里再次没有证明)对于所有 m,整数 2m = z 中的 z 意味着 z 不等于 m,给定 m 不是 0。在 n 为 0 的情况下,2*0 = 0所以 0 即使我们完成了(如果 n = 0 则 0 在 C 整数中,因为 n 在函数中的 C 整数中even
,因此 k = 0 在 C 整数中)。因此,如果 n 是偶数,则对于 C 整数中的 n 存在这种 C 整数中的 ak。
一个类似的论点表明,如果 n 是奇数,则在 C 整数中存在 ak,使得 n = 2k + 1。
因此,这里介绍的函数even
将odd
适用于所有 C 整数。
// C#
bool isEven = ((i % 2) == 0);
这是Java中的答案:
public static boolean isEven (Integer Number) {
Pattern number = Pattern.compile("^.*?(?:[02]|8|(?:6|4))$");
String num = Number.toString(Number);
Boolean numbr = new Boolean(number.matcher(num).matches());
return numbr.booleanValue();
}
阅读这个相当有趣的讨论,我记得我有一个真实世界的时间敏感函数,可以在主循环中测试奇数和偶数。这是一个整数幂函数,发布在 StackOverflow 的其他地方,如下所示。基准非常令人惊讶。至少在这个现实世界的函数中,模数更慢,而且明显如此。优胜者,需要 67% 的模时间,是一个 or (|) 方法,并且在此页面的其他地方找不到。
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;
}
对于 3 亿次循环,基准时间如下。
3.962 | 和掩码方法
4.851 & 方法
5.850% 方法
对于那些认为理论或汇编语言列表来解决此类论点的人来说,这应该是一个警示故事。霍拉旭,天地间的事情比你的哲学梦想的还要多。
试试这个:return (((a>>1)<<1) == a)
例子:
a = 10101011
-----------------
a>>1 --> 01010101
a<<1 --> 10101010
b = 10011100
-----------------
b>>1 --> 01001110
b<<1 --> 10011100
这是与@RocketRoy 就他的回答进行讨论的后续行动,但它可能对任何想要比较这些结果的人有用。
tl;dr从我所见,Roy 的方法 ( (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));
}
带有 -O3 的 CLang 3.9.0:
isOdd_mod(unsigned int): # @isOdd_mod(unsigned int)
and edi, 1
mov eax, edi
ret
isOdd_and(unsigned int): # @isOdd_and(unsigned int)
and edi, 1
mov eax, edi
ret
isOdd_or(unsigned int): # @isOdd_or(unsigned int)
and edi, 1
mov eax, edi
ret
带有 -O3 的 GCC 6.2:
isOdd_mod(unsigned int):
mov eax, edi
and eax, 1
ret
isOdd_and(unsigned int):
mov eax, edi
and eax, 1
ret
isOdd_or(unsigned int):
or edi, -2
xor eax, eax
cmp edi, -1
sete al
ret
向 CLang 致敬,它意识到这三种情况在功能上是相同的。但是,Roy 的方法没有在 GCC 中进行优化,所以 YMMV。
与 Visual Studio 类似;检查这三个函数的反汇编版本 x64 (VS2015),我可以看到比较部分对于“mod”和“and”情况是相等的,而对于 Roy 的“or”情况则稍大一些:
// 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)
但是,在运行实际基准测试以比较这三个选项(普通 mod、按位或、按位与)后,结果完全相等(同样,Visual Studio 2005 x86/x64,发布版本,未附加调试器)。
发布汇编使用and case 的test
指令,而 Roy 的 case 使用了这种方法,但它被大量展开和优化,因此在实践中没有区别。and
mod
cmp eax,0FFFFFFFFh
我运行 20 次后的结果(i7 3610QM,Windows 10 电源计划设置为高性能):
[测试:普通模式 2] 平均时间:689.29 毫秒(相对差异:+0.000%) [测试:按位或]平均时间:689.63 毫秒(相对差异:+0.048%) [测试:按位和]平均时间:687.80 毫秒(相对差异:-0.217%)
这些选项之间的差异小于 0.3%,因此很明显组装在所有情况下都是相等的。
如果有人想尝试,这里是代码,但需要注意的是我只在 Windows 上测试过它(检查定义的#if LINUX
条件get_time
并在需要时实现它,取自这个答案)。
#include <stdio.h>
#if LINUX
#include <sys/time.h>
#include <sys/resource.h>
double get_time()
{
struct timeval t;
struct timezone tzp;
gettimeofday(&t, &tzp);
return t.tv_sec + t.tv_usec*1e-6;
}
#else
#include <windows.h>
double get_time()
{
LARGE_INTEGER t, f;
QueryPerformanceCounter(&t);
QueryPerformanceFrequency(&f);
return (double)t.QuadPart / (double)f.QuadPart * 1000.0;
}
#endif
#define NUM_ITERATIONS (1000 * 1000 * 1000)
// using a macro to avoid function call overhead
#define Benchmark(accumulator, name, operation) { \
double startTime = get_time(); \
double dummySum = 0.0, elapsed; \
int x; \
for (x = 0; x < NUM_ITERATIONS; x++) { \
if (operation) dummySum += x; \
} \
elapsed = get_time() - startTime; \
accumulator += elapsed; \
if (dummySum > 2000) \
printf("[Test: %-12s] %0.2f ms\r\n", name, elapsed); \
}
void DumpAverage(char *test, double totalTime, double reference)
{
printf("[Test: %-12s] AVERAGE TIME: %0.2f ms (Relative diff.: %+6.3f%%)\r\n",
test, totalTime, (totalTime - reference) / reference * 100.0);
}
int main(void)
{
int repeats = 20;
double runningTimes[3] = { 0 };
int k;
for (k = 0; k < repeats; k++) {
printf("Run %d of %d...\r\n", k + 1, repeats);
Benchmark(runningTimes[0], "Plain mod 2", (x % 2));
Benchmark(runningTimes[1], "Bitwise or", (0xFFFFFFFF == (x | 0xFFFFFFFE)));
Benchmark(runningTimes[2], "Bitwise and", (x & 1));
}
{
double reference = runningTimes[0] / repeats;
printf("\r\n");
DumpAverage("Plain mod 2", runningTimes[0] / repeats, reference);
DumpAverage("Bitwise or", runningTimes[1] / repeats, reference);
DumpAverage("Bitwise and", runningTimes[2] / repeats, reference);
}
getchar();
return 0;
}
我知道这只是语法糖,仅适用于.net,但是扩展方法呢...
public static class RudiGroblerExtensions
{
public static bool IsOdd(this int i)
{
return ((i % 2) != 0);
}
}
现在您可以执行以下操作
int i = 5;
if (i.IsOdd())
{
// Do something...
}
在“创意但令人困惑的类别”中,我提供:
int isOdd(int n) { return n ^ n * n ? isOdd(n * n) : n; }
此主题的变体,特定于 Microsoft C++:
__declspec(naked) bool __fastcall isOdd(const int x)
{
__asm
{
mov eax,ecx
mul eax
mul eax
mul eax
mul eax
mul eax
mul eax
ret
}
}
按位方法取决于整数的内部表示。模数将在任何有模数运算符的地方工作。例如,某些系统实际上使用低级位进行标记(如动态语言),因此原始 x & 1 在这种情况下实际上不起作用。
IsOdd(int x) { 返回真;}
正确性证明 - 考虑所有正整数的集合,并假设有一组非奇数的非空整数。因为正整数是有序的,所以会有一个最小的非奇数,它本身就很奇数,所以很明显这个数字不可能在集合中。因此这个集合不能是非空的。重复负整数,除了寻找最大的非奇数。
便携的:
i % 2 ? odd : even;
不可携带:
i & 1 ? odd : even;
i << (BITS_PER_INT - 1) ? odd : even;
正如一些人所发布的,有很多方法可以做到这一点。根据这个网站,最快的方法是模数运算符:
if (x % 2 == 0)
total += 1; //even number
else
total -= 1; //odd number
然而,这里有一些其他的代码是作者标记的,它比上面的普通模运算运行得慢:
if ((x & 1) == 0)
total += 1; //even number
else
total -= 1; //odd number
System.Math.DivRem((long)x, (long)2, out outvalue);
if ( outvalue == 0)
total += 1; //even number
else
total -= 1; //odd number
if (((x / 2) * 2) == x)
total += 1; //even number
else
total -= 1; //odd number
if (((x >> 1) << 1) == x)
total += 1; //even number
else
total -= 1; //odd number
while (index > 1)
index -= 2;
if (index == 0)
total += 1; //even number
else
total -= 1; //odd number
tempstr = x.ToString();
index = tempstr.Length - 1;
//this assumes base 10
if (tempstr[index] == '0' || tempstr[index] == '2' || tempstr[index] == '4' || tempstr[index] == '6' || tempstr[index] == '8')
total += 1; //even number
else
total -= 1; //odd number
有多少人甚至知道Math.System.DivRem方法,或者他们为什么要使用它?
int isOdd(int i){
return(i % 2);
}
完毕。
为了给我们这些在学习期间没有做太多布尔代数的人详细说明按位运算符方法,这里有一个解释。可能对 OP 没有多大用处,但我想弄清楚为什么 NUMBER & 1 有效。
请注意,就像上面有人回答的那样,表示负数的方式可能会阻止此方法的工作。事实上,它甚至可以破坏模运算符方法,因为每种语言在处理负操作数的方式上可能不同。
但是,如果您知道 NUMBER 将始终为正,则此方法效果很好。
正如上面的 Tooony 所指出的,只有二进制(和十进制)中的最后一个数字很重要。
布尔逻辑与门规定两个输入都必须为 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
}
对不起,如果这是多余的。
数字零奇偶校验 | 零http://tinyurl.com/oexhr3k
Python 代码序列。
# 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
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,则为偶数。在小端系统上,比如英特尔的 x86 架构,它会是这样的:-
if (iToTest & 1) {
// Even
} else {
// Odd
}
如果您想提高效率,请使用按位运算符 ( x & 1
),但如果您想可读,请使用模 2 ( x % 2
)
检查偶数或奇数是一项简单的任务。
我们知道任何能被 2 整除的数都是偶数,否则是奇数。
我们只需要检查任何数字的可分性,并且我们使用%
运算符来检查可分性
使用 if else 检查奇数
if(num%2 ==0)
{
printf("Even");
}
else
{
printf("Odd");
}
使用条件/三元运算符
(num%2 ==0) printf("Even") : printf("Odd");
使用按位运算符
if(num & 1)
{
printf("Odd");
}
else
{
printf("Even");
}
+66%更快 >!(i%2) / i%2 == 0
int isOdd(int n)
{
return n & 1;
}
代码检查整数的最后一位是否为二进制中的1
解释
Binary : Decimal
-------------------
0000 = 0
0001 = 1
0010 = 2
0011 = 3
0100 = 4
0101 = 5
0110 = 6
0111 = 7
1000 = 8
1001 = 9
and so on...
请注意,对于奇数,最右边的位始终为 1 。
&按位与运算符检查返回行中最右边的位是否为 1
认为它是真假
当我们将n与1进行比较时,这意味着0001
二进制(零的数量无关紧要)。
那么让我们想象一下,我们有一个大小为 1 字节的整数n 。
它将由 8 位 / 8 二进制数字表示。
如果 int n是7并且我们将它与1进行比较,就像
7 (1-byte int)| 0 0 0 0 0 1 1 1
&
1 (1-byte int)| 0 0 0 0 0 0 0 1
********************************************
Result | F F F F F F F T
其中F代表假,T代表真。
如果它们都是真的,它只比较最右边的位。因此,自动
7 & 1
为真。
如果我想检查最右边的位怎么办?
只需将其更改n & 1
为n & 2
20010
在二进制中表示,依此类推。
如果您是按位运算的初学者,我建议使用十六进制表示法
return n & 1;
>> return n & 0x01;
。
模运算符 '%' 可用于检查一个数是奇数还是偶数。即当一个数除以 2 时,如果余数为 0,则其为偶数,否则为奇数。
#include <stdio.h>
int main()
{
int n;//using modulus operator
scanf("%d",&n);//take input n from STDIN
printf("%s",n%2==0?"Even":"Odd");//prints Even/Odd depending on n to STDOUT
return 0;
}
但是使用位操作比上面的方法快得多,所以如果你取一个数字并在逻辑上应用“&”,如果答案是 1 那么它的偶数是奇数。基本上我们必须检查最后一位二进制中的数字 n。如果最后一位为 0,则 n 为偶数,否则为奇数。
例如:假设 N = 15 ,二进制 N = 1111 ,现在我们将其与 1
1111
0001
&-----
0001
由于结果为 1,因此数字 N=15 为奇数。
同样,假设 N = 8 ,二进制 N = 1000 ,现在我们将其与 1
1000
0001
&-----
0000
由于结果为 0,因此数字 N=8 为偶数。
#include <stdio.h>
int main()
{
int n;//using AND operator
scanf("%d",&n);//take input n from STDIN
printf("%s",n&1?"Odd":"Even");//prints Even/Odd depending on n to STDOUT
return 0;
}