二进制总结

1.编码

	正数	负数
原码	0本体	1本体
补码	0本体	按位取反+1(符号位始终为1)
反码	0本体	按位取反(符号位始终为1)

2.分类

有符号:

无符号:

3. 位运算

3.1 与、或、异或


与(&)	0&0=0	1&0=0	1&1=1
或(\|)	0\|0=0	0\|1=1	1\|1=1
异或(^)	0^0=0	1^0=1	1^1=0

3.2 左移

m<<n

表示把m左移n位。往左移n位的时候，最左边的n位将被丢弃，同时在最右边补上n个0.

exp：

00001010<<2=00101000

10001010<<3=01010000

3.3 右移

m>>n

表示把m右移n位。往右移的时候，最右边的n位将被丢弃。

如果数字之前是一个正数，则右移之后在最左边补n个0；

如果数字之前是一个负数，则右移之后在最左边补n个1.

exp:

00001010>>2=00000010

10001010>>3=11110001

3.4 应用

3.4.1 移位运算代替乘除法

3.4.2 右移一位 == 除以2

3.4.3 左移一位 == 乘以2

二进制中1的个数

int NumberOf1(int n)
{
    int count = 0;
    while(n)
    {
        ++count;
        n = (n-1) & n;
    }
    return count;
}

不用加减法做加法

int Add(int num1,int num2)
{
    int sum,carry;
    do
    {
        sum = num1 ^ num2;
        carry = (num1 & num2) << 1;
        num1 = sum;
        num2 = carry;
    } 
    while(num2 !=0 );
    
    return num1;
}

4.实战中常见的位运算

6(10)=0110(2)
5(10)=0101(2)
-6(10)=1010(2)

1.判断奇偶性 (x %2 == 1)X & 1 == 1 OR == 0

0110&0001=0 偶数

2.清除最低位的1X = X & (X-1)

0110&0101=0100

3.得到最低位的1X & (-X)

0110&1010=0010

更为复杂的位运算操作
1.将x最右边的n位清零x & ( ~ 0 << n )

2.获取x的第n位值( x >> n ) & 1

3.获取x的第n位的幂值x & ( 1 << ( n - 1 ) )

4.仅将第n位置位1x | ( 1 << n )

5.仅将第n位置位0x & ( ~ ( 1 << n ) )

6.将x的最高位值第n位（含）清零x & ( ( 1 << n ) - 1 )

7.将第n位至第0位（含）清零x & ( ~ ( ( 1 << ( n + 1 ) ) - 1 ) )

wade's tech blog