数学相关 - Wiki

数学相关

Table of Contents

进制转换

灵活利用取整取余

例如二进制计算：a + b + carry = s ; remainder = s / 2; carry = s % 2

利用公式的转换，把加法变为减法，避免溢出。利用结论：只有符号相同的整数相加才有可能才生溢出(overflow).

a + b > INT_MAX  ==> a > INT_MAX – b
a + b < INT_MIN  ==> a < INT_MIN - b

2^n = 00..100..0
2^n-1 = 00...011..1  ==> n & (n - 1) == 0
2^n & 2^n-1 = 0

符号	描述	运算规则
&	与	两个位都为1时，结果才为1
\		或
^	异或	两个位相同为0，相异为1
~	取反	0变1，1变0
<<	左移	各二进位全部左移若干位，高位丢弃，低位补0
>>	右移	各二进位全部右移若干位，对无符号数，高位补0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移）

java 中逻辑右移的符号为 >>> ，默认的 >> 是算术右移

判断奇偶

只要根据最未位是0还是1来决定，为0就是偶数，为1就是奇数。
```
if ((a & 1) == 0)
```
交换两数
1. a^=b 即a=(a^b);
2. b^=a 即b=b^(a^b)，由于^运算满足交换律，b^(a^b)=b^b^a。由于一个数和自己异或的结果为0并且任何数与0异或都会不变的，所以此时b被赋上了a的值。
3. a^=b 就是a=a^b，由于前面二步可知a=(a^b)，b=a，所以a=a^b即a=(a^b)^a。故a会被赋上b的值。
  
  a ^= b; b ^= a; a ^= b;
变换符号

取反后加一
```
~a + 1
```
绝对值 k 对于任何数，与0异或都会保持不变，与-1即0xFFFFFFFF异或就相当于取反。因此，a与i异或后再减i（因为i为0或-1，所以减i即是要么加0要么加1）也可以得到绝对值。
```
int i = a >> 31;
return ((a ^ i) - i);
```

例题：正整数378000共有多少个正约数？解：将378000分解质因数378000=2^4×3^3×5^3×7^1 由约数个数定理可知378000共有正约数(4+1)×(3+1)×(3+1)×(1+1)=160个。