灵活利用取整取余
例如二进制计算: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)
交换两数
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个。