Date:2012-11-08
1.位运算基本
1.overview
C语言中位运算有: and ,or , xor, not ,shift left,shift right
+---+---+-----+-----+-----+----+ | a | b | a&b | a|b | a^b | ~a | +---+---+-----+-----+-----+----+ | 0 | 0 | 0 | 0 | 0 | 1 | +---+---+-----+-----+-----+----+ | 0 | 1 | 0 | 1 | 1 | 1 | +---+---+-----+-----+-----+----+ | 1 | 0 | 0 | 1 | 1 | 0 | +---+---+-----+-----+-----+----+ | 1 | 1 | 1 | 1 | 0 | 0 | +---+---+-----+-----+-----+----+
2.各自特色
and: 可以判断出位元是不是1, 可以强制标0
例如对整数n的位元中是1的计数:
#define INT_BITS sizeof(int)*8 //number of bits of integer int count_bit_1(int n) { int i, j; for (i = 0, j = 0; i < INT_BITS; i++) if (n & (1 << i)) j++; return j; }
or: 可以把位元强制置1
例如, 我们把整数n的第五位标1: n|(1 << 4)
xor: 0^1 => 1, 1^1 => 0, 可以看出异或可以颠倒位元的值
例如我们要把n的第五位颠倒:n^(1 << 4)
2.基本技巧
1.一些等式
~a+1=-a (求相反数是:取反再加一)
~(a+b)=~a+~b+1
证明:~(a+b)=-(a+b)-1=(-a-1)+(-b-1)+1=~a+~b+1 (依据公式~a=-a-1)
a^a=0
a^0=a
a^b=b^a (交换律)
(a^b)^c=a^(b^c) (结合律)
(~a)^b=a^(~b)=~(a^b) (可以枚举归纳证之)
c=a^b => b=a^c
证:c=a^b => a^c=a^a^b => a^c=0^b => a^c=b
(a-1)^(-a)=-1
证明:令b=-a 即证 (-b-1)^b=-1 即证 ~b^b=-1 : ~b^b=~(b^b)=~0=-1
2.应用技巧
1.整数奇偶性判断
a&1可以判断a的奇偶性.二进制的末位为1表示为奇数,否则偶数
2.判断整数的符号
#define INT_BITS sizeof(int)*8 //number of bits of integer int signof(int n) { return n >> INT_BITS-1; }
返回-1表示负数,返回0表示非负数
3.计算整数的绝对值
int abs(int n) { int sign = n >> INT_BITS-1; return (n+sign)^sign; }
当n是非负整数的时候, n^0 = n = abs(n)
当n是负数的时候, (n-1)^-1 = -n = abs(n)
4.不用临时变量交换两个整数变量
#define SWAP(x, y) (x) ^= (y) ^= (x) ^= (y)
或者更'详细'些:
a = a^b; b = a^b; a = a^b;
证明 :令t = a, s = b.用t, s保留原值.
a = a^b => a = t^s
b = a^b => b = (t^s)^s = t^(s^s) = t^0 = t
a = a^b => a = (t^s)^t = s^(t^t) = s
5.判断整数是不是2的整数幂
x & (x&(x-1))
6.左移, 右移
左移1位相当于乘以2, 右移相当于除以2