数学相关
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的指数

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 中逻辑右移的符号为 >>> ,默认的 >> 是算术右移

技巧

  1. 判断奇偶

    只要根据最未位是0还是1来决定,为0就是偶数,为1就是奇数。

    if ((a & 1) == 0)
    
  2. 交换两数

    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;

  3. 变换符号

    取反后加一

    ~a + 1
    
  4. 绝对值 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个。

质数个数定理