CTF-RE 从0到N: 理解基本模运算

2024/10/27 14:34:37 来源：https://blog.csdn.net/weixin_59166557/article/details/143265629 浏览: 次关键词：CTF-RE 从0到N: 理解基本模运算

**模运算（Modular Arithmetic）**是数学和计算机科学中常用的运算，它计算两个整数相除后的余数。模运算的符号通常是%，比如a % n表示a除以n后的余数。

1. 判断奇偶性

使用 % 2 可以快速判断一个整数是奇数还是偶数：

int number = 7;
if (number % 2 == 0) {printf("Even\n");
} else {printf("Odd\n");
}

作用：可以高效地分类奇数和偶数，在一些算法中仅需要操作奇数或偶数时非常有用。

2. 环形数组或循环列表

在处理环形数组（例如循环缓冲区）时，模运算可以帮助实现索引的循环效果：

int arr[] = {10, 20, 30, 40, 50};
int length = sizeof(arr) / sizeof(arr[0]);
for (int i = 0; i < 10; i++) {printf("%d ", arr[i % length]); // 使用 % 确保索引在 0 到 length-1 之间循环
}

作用：在环形缓冲区或循环列表中使用 % 可以避免索引越界，保持指针始终在有效范围内循环。

3. 哈希函数中的索引计算

在哈希表算法中，模运算用于将哈希值映射到数组索引：

int hash = key % table_size; // 将 key 映射到表的大小范围内
hash_table[hash] = value;

作用：通过模运算，将任意整数键值映射到哈希表的索引范围中，使哈希表更均匀地分布数据，减少冲突。

4. 找到一个数的周期性结果

当处理周期性问题时，模运算可以帮助找到一个数在周期中的位置。例如，计算钟表时间的循环：

int hour = (current_hour + added_hours) % 12;

作用：可以在12小时制时钟中，计算出添加时间后的具体小时数，而不会超过12小时。

5. 数组中的“跳跃”算法

模运算可以用来在数组中实现按固定步长的跳跃。例如，在圆形数组上按特定步长跳跃：

int arr[] = {1, 2, 3, 4, 5};
int length = sizeof(arr) / sizeof(arr[0]);
int start = 0;
int step = 2;
for (int i = 0; i < length; i++) {printf("%d ", arr[(start + i * step) % length]);
}

作用：在按特定步长跳跃时，可以保持在数组范围内循环，避免索引越界。

6. 判断年份是否为闰年

在判定一个年份是否为闰年时，模运算被广泛应用。规则是年份必须被4整除，但不能被100整除，或必须被400整除：

int year = 2024;
if ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0) {printf("Leap year\n");
} else {printf("Not a leap year\n");
}

作用：使用模运算判断年份特性，用于时间和日期算法中。

7. 循环位移问题

在某些循环位移或轮换问题中，模运算可以帮助计算目标位置。例如，在将数组向右移动k个位置时，可以通过模运算计算新的索引位置：

int arr[] = {1, 2, 3, 4, 5};
int length = sizeof(arr) / sizeof(arr[0]);
int k = 2;
for (int i = 0; i < length; i++) {int new_pos = (i + k) % length;printf("%d ", arr[new_pos]);
}