位运算

位运算

判断奇偶数

/* 一个数如果是奇数，那么它对应二进制数最后一位一定是1，偶数一定是0
    方法  ：判断 x & 1 的返回值
    x&1==1 奇数
    x&1==0 偶数
*/

获取二进制位是1还是0

/*
 需要借助 位运算符 与 1进行&运算
 假如数 是 101101  就是把每一位移动到最后一位  & 1 来判断 1 可以写成0000 0001
 这样的话就能通过& 的结果来判断当前位是 1 还是 0
*/


// 输出一个数 的32位二进制形式
  #include<iostream>

    using namespace std;
    int main()
    {
        int n;
        cin>>n;
      for(int i=31;i>=0;i--)
      {
          printf("%d",(n>>i)&1);
      }


        return 0;
    }

n&(n-1)

• 可以把 一个数 对应的 二进制数 去掉 最低位的1 使它变成 0

• 应用

  判断十进制数对应二进制数中 1 的个数

  int find_number(int x)
  {
      int count = 0;
      while(x)        //  把 后面的1 全部剪掉 直到 二进制位数全为0 值对应0
      {
          count++;        // 先 加一  在  &
          x&=(x-1);
      }
      return count;
  
  }
  

  判断一个数是否是2 的次幂

    // 如果一个数 n 是2 的次幂，那么他的 二进制表示中只有 一位 是 1 其余是 0 
    // 根据 n&(n-1) ==0
  
      if(n&(n-1) == 0)
        printf("Yes")；
  
  

求一个二进制数中0 的个数

1. 直到字节数 int 是4 字节 32位 32- 1的数目

2. 假如x是一个二进数，例如x=0xfffa(1111 1111 1111 1010)，要实现去掉最低位一个0，可进行的操作是x|=(x+1)，此时x0xfffb(1111 1111 1111 1011) ；再去掉一个0，同样，x|=(x+1)，则x0xffff。如果x的2字节表示，则(x+1)为0。

   基于该思想，利用while循环对(x+1)判断，可实现计算二进制数中所有位上0的个数。注意，x=1时，1的高位默认有0的（注意是所有位而不是写出来的位上，因为二进制高位的0是默认不写出来的，但是不写出来不代表没有啊）。

   int findnumber(int x)
   {
       int cnt=0;
       while(x+1)
       {
       cnt+=1;
           x|=(x+1);    // 0 的个数 一部分由它的 数据类型决定 int 是 32 位
       }
   }
   

求一堆数中 只出现一次的数

• 利用 异或 的性质

  • 一个数 一异或 它本身 是 0，0 异或任何一个数是该数本身
  • 交换律 （可以不用管先后顺序）

• int n;
  cin>>n;
  while(n--)
  {
      int x;
      cin>>x;
      ans^=x;
  }
  cout<<ans;
  

不借助 中间变量 来交换两个数的值

• 利用位异或

  a=a^b;
  b=a^b;
  a=a^b;
  

• 补充

  a+=b;
  b=a-b;
  a-=b;
  

实现字符的大小写转换

• ‘ 字符’ 异或 32 大写变小写，小写变大写

  #include<iostream>
  
  using namespace std;
  int main()
  {
      int len;
      string a;
      cin>>a;
      len=sizeof(a);
  
  
      for(int i=0;i<len;i++)
       a[i]^=(1<<5); // char^ 32
       cout<<a;
  
      return 0;
  }
  
  

求整数的绝对值

我们知道在我们对一个数进行位运算的时候，是在这个数的补码上进行的，对于补码我们知道，正数的补码是原码，负数的补码为原码除了最高位的符号位，取反，然后加1。把补码转换成原码的时候，正数还是原码，负数时把补码除了符号位取反然后加1(我们可以发现如果这时候连符号位也求反，然后加1，与以前不同的只是少了一个符号位，现在实际上就是这个数的绝对值)。所以我们可以得到对一个负数求绝对值的表达式为

int SignReversal(int a) 

{ 

  return ~a + 1; 

}

那么由这些知识我们可以很快地得到求一个数的绝对值的表达式：

先移位来取符号位，int i = a >> 31;要注意如果a为正数，i等于0，为负数，i等于-1。然后对i进行判断——如果i等于0，直接返回。否之，返回~a+1。完整代码如下：

int my_abs(int a) 
{ 
  int i = a >> 31; 
  return i == 0 ? a : (~a + 1); 
} 

现在再分析下。对于任何数，与0异或都会保持不变，与-1即0xFFFFFFFF异或就相当于取反。因此，a与i异或后再减i（因为i为0或-1，所以减i即是要么加0要么加1）也可以得到绝对值。所以可以对上面代码优化下：

int my_abs(int a) 
{ 
    int i = a >> 31; 
   return ((a ^ i) - i); 
 }