Contents

1. 1. 用bit进行基本运算
   1. 1.1. 奇偶性
   2. 1.2. 平均值
   3. 1.3. 交换变量值
   4. 1.4. 2的幂
   5. 1.5. 绝对值
2. 2. 常见bit基本操作
   1. 2.1. Get Bit
   2. 2.2. Set Bit
   3. 2.3. Clear Bit
      1. 2.3.1. 清除第i位
      2. 2.3.2. 清除从第i位到最高位（包括i）
      3. 2.3.3. 清除从第0位到第i位
      4. 2.3.4. 清除第i位到第j位(i<=j)
   4. 2.4. Update Bit

用bit进行基本运算

奇偶性

判断int型变量a的奇偶性
a&1=0 偶数
a&1=1 奇数

平均值

给定两个int型变量，要求用先求和后除以2的方法求二者平均值

public staitc int average(int x,int y){
	return (x+y)>>1;
}

上面方法x+y的值可能直接超过int类型的最大范围，优化做法：

public static int average(int x,int y){
    return ((x^y)>>1)+(x&y);
    /*(x^y) >> 1得到x，y其中一个为1的位并除以2， 
    x&y得到x，y都为1的部分，加一起就是平均数了*/  	
}

交换变量值

给定两个int型变量，不用额外的变量交换两个变量的值

public static void swap(int x,int y){
	x^=y;
	y^=x;
	x^=y;
}

2的幂

给定一个整数n，判断n是否是2的幂

public boolean isPowerOf2(int n){
	return ((n!=0)&&(n&(n-1)==0));
}

绝对值

public static int abs(int x){
	int y=x>>31;
	return (x^y)-y;
	/* x>>31 取得x的符号，若x为正数，x>>31等于0，若n为负数，x>>31等于-1 
若x为正数 x^0=x,x不变，若x为负数有x^-1,结果x变号并且为x的绝对值减1，再减去-1就是绝对值 */ 
}

常见bit基本操作

Get Bit

通过把1左移i位获得形如00010000形式的数然后与所给数num进行&运算，这样就把num除了第i位的数字全都清除掉，然后判断它是否为0,若不为0则说明第i位是1,返回true,反之是0（false）

public static boolean getBit(int num,int i){
	return ((num&(1<<i))!=0);
}

Set Bit

通过把1左移i位获得形如00010000形式的数然后与所给数num进行|运算，这样既把第i位set为1,又保留了其它位的原始值

public static int setBit(int num,i){
	return (num|(1<<i));
}

Clear Bit

清除第i位

方法与Set Bit相反，先获得00010000形式的数然后取反（~）得11101111形式然后与num进行&运算，就能将第i位清除（实际是置0）

public static int clearBit(int num,int i){
	int mask=~(1<<i);
	return num&mask;
}

清除从第i位到最高位（包括i）

先将1左移i位，此时第i位（i从0开始）是1，然后将该数-1得到00001111的形式（eg:i=4），然后与num&运算

public static int clearBit2(int num,int i){
	int mask=(1<<i)-1;
	return num&mask;
}

清除从第0位到第i位

先得到一个所有位全1的数，然后左移i+1位，此时得到从第0位到第i位均为0的数，形如11110000（eg:i=3），然后与num&运算

public static int clearBit3(int num,int i){
	int allOnes=~0;
	int mask=allOnes<<i+1;
	return num&mask;
}

清除第i位到第j位(i<=j)

结合清除i~最高位和0～i位两个方法

public static int clearBit4(int num,int i,int j){
	int allOnes=~0;
	int left=allOnes<<(j+1);
	int right=(1<<i)-1;
	int mask=left|right;
	return num&mask;
}

Update Bit

update是clear和set的结合，将num第i位修改为v：先clear第i位，然后set第i位，注意set之前先将v左移到第i位

public static int updateBit(int num,int i,int v){
	int mask=~(1<<i)
	return (num&mask)|(v<<i);
}