整除运算与取模运算

2019-04-13 13:41发布

凡是呈现明显周期性的,比如十二生肖(以十二为周期),比如星期(以 7 为周期),比如天干(以 10 为周期),比如地支(以 12 为周期),最佳的解决方案就是取模(或者简单地说对该周期取余数)。
  • 两个整数间能够整除(余数为 0)的全部意义正在于 ⇒ 实现均分;
    • 10 个小朋友,两两分组,共分 5 组;
    • 10 个小朋友,55分组,共分 2 组;
    • 在比如质数个小朋友(如 7 个),就没办法实现均匀的分配人数了;
  • 在 C语言的环境下,将一个整数对 2 不断地做整除:
    • 0/2 ⇒ 0, 1/2 ⇒ 0
    • 2/2 ⇒ 1, 3/2 ⇒ 1,
    • 4/2 ⇒ 2, 2/2 ⇒ 1
    • 5/2 ⇒ 2, 2/2 ⇒ 1
    也即除了 0/1 之外的任何正整数,不论是奇数还是偶数,不断地对 2 整除的最终结果都会是 1;
    15/2 = 7 /2 = 3 /2 =1

1. 截断低位与抹除高位

如果一个数(二进制形式 n 位)对 2k 整除和取模:
  • (1)整除是截断低位(k),保留高位(n-k);
  • (2)取模运算是抹除最高比特位(要求 k = n-1);
不妨以 10(1010) 和 8(1000) 为例:
  • (1)整除:10/8 == 1
  • (2)取模:10%8 == 010 == 2

2. 整除:降低分辨率,取模运算:转换值域

  • 整除:降低分辨率,
  • 取模:转换值域

2.1 整除

[0,5)50[5,10)51[5n,5n+1)5n

2.2 取模

x%5[0,5)/0,1,2,3,4x%N[0,N)/0,1,2,,N1

3. 计算星期几

3.0 计算十天后是星期几

10%7=3 就以今天 2016 年 6 月 22 为星期三,一周也即 7 天后的仍是星期三,则10天后是星期六,10 对 7 取模的含义正在与,获取余数,3(星期三)+3(余数3) = 6。

3.1 计算元旦的星期

计算星期几,不可避免地要同 7 的取模运算挂上联系。
  • 平年:365天,52 周余 1 天;
  • 闰年:366天,52 周余 2 天;
2016 年的元旦是星期 5,则 2017 年元旦是星期星期日(5+2=7),2016年是闰年。

3.2 计算任意一天的一年后的这一天是星期几

我们继续升级这一问题,计算任意一天的一年后的这一天是星期几。这道题目比计算元旦稍微复杂的是,需要判断这一天到一年后的今天所跨越的 2 月是有 28 天还是 29 天,而不直接取决当年是否是闰年。 以 2016 年 6 月 22 日为例,这一天是星期三,则一年后的今天,即 2017 年 6 月 22 是星期几? 从 2016 年 6 月 22 到 2017 年 6 月 22 中间经历的 2 月,是 2017 年的二月,28天,也即从 2016年 6 月 22 到 2017 年 6 月22,所经历的一年是 365 天。 则 2017 年 6 月 22 是 星期 4 (3 + 1).

4. 计算十二生肖

  • (1)鼠,(2)牛,(3)老虎,(4)兔
  • (5)龙,(6)蛇,(7)马,(8)羊
  • (9)猴,(10)鸡,(11)狗,(12)猪
查阅万年历可知:1900 年是鼠年,2000 年是龙年, 比如我们要计算 1987 年的属相,87 % 12 = 3,鼠年之后的第四年,那就是 4 兔。 比如我们要获得 2016 年的属相,16 % 12 = 4,龙年之后的第四年,那就是 4+5 = 9 猴年。

5. 限定范围

一个数对 A 取模,所得的结果要小于 A,取模相当于除法运算的求余,余数自然小于除数;