位操作

c++中位操作操作符

符号	描述	规则
&	按位取与	有0得0
		按位取或	有1得1
^	异或	不同得1
~	取反	01颠倒
<<	左移	向左移动后面的位数，溢出抛弃，添零补位
>>	右移	右移后面的位数，移出抛弃，添零补位

这些位操作符只能用于整形的操作，其他会编译报错。
位操作符的运算优先级比较低，因为尽量使用括号来确保运算顺序。
另外位操作还有一些复合操作符，如&=、|=、^=、<<=、>>=。

常用位操作技巧

判断奇偶

// 取最后一位，判断是1则为奇数，是0则为偶数。
int judge(int a)
{
  return a & 1;
}

交换数字

// a=(a^b)^(a^b)^b=b 
// b=(a^b)^b=a
void swap(int &a, int &b)
{
  if (a != b)
  {
    a ^= b;
    b ^= a;
    a ^= b;
  }
}

变换符号

取反加1

A = (~A) +1;

求绝对值

\\ 先判断正负再变换符号

\\ 判断正负根据数字的第一位是1则为负
if (a >> 32) 
{
  a = (~a) + 1
}

无+-号计算加法

// 首先取ab的与和异或，与表示都为1的位，若不为零，则需要进位。
// 异或中不同为1，相同为零，效果与加法相似，只是没有进位。
// 若有进位在异或结果上加上与的结果左移一位的结果即可。
int sum(int a, int b)
{
  int c = a & b, d = a ^ b;
  return c == 0 ? d : sum(d, c << 1); 
}

高底位交换

// 左移加右移。假设是16位数字。
a = (a << 8) | (a >> 8)

统计1的个数

// 假设对于16位数字
// 相邻两个1位相加
a = ((a & 0xAAAA) >> 1) + ((a & 0x5555))
// 相邻两个2位相加
a = ((a & 0xCCCC) >> 2) + ((a & 0x3333))
// 相邻两个4位相加
a = ((a & 0xF0F0) >> 4) + ((a & 0x0F0F))
// 相邻两个8位相加
a = ((a & 0xFF00) >> 8) + ((a & 0x00FF))
// 最后得到的数字就是1的个数

二进制数字翻转

// 假设对于16位数字
// 相邻两个1位交换
a = ((a & 0xAAAA) >> 1) | ((a & 0x5555) << 1)
// 相邻两个2位交换
a = ((a & 0xCCCC) >> 2) | ((a & 0x3333) << 2)
// 相邻两个4位交换
a = ((a & 0xF0F0) >> 4) | ((a & 0x0F0F) << 4)
// 相邻两个8位交换
a = ((a & 0xFF00) >> 8) | ((a & 0x00FF) << 8)