位运算_牛客博客

前提：二进制存储方式
正数：符号位为0，其他位正常存储
负数：符号位为1，其他位按照补码方式存储；
无符号：和正数一样，但是没有符号位；

1.&（与）
1&1=1；1&0=0；0&1=0；0&0=0；
总结：只有两边都是1时才等于一；
例如：3&5 即 0000 0011& 0000 0101 = 00000001 因此，3&5的值为1。
用处；
（1）清零。如果想将一个单元清零，即使其全部二进制位为0，只要与一个各位都为零的数值相与，结果为零。
例：3&0=0；0000 0011&0000 0000=0；
（2）判断二进制指定位置的数，并将其他位清空。将指定位变成1其他位为0，
例： a=0000 1011;
a&0000 0011=0000 1011 & 0000 0011=0000 0011;
（3）判断奇偶：

if(a&1)
{
    cout<<"奇数"<<endl;
}
else
{
    cout<<"偶数"<<endl;
}

| (或)
0|0=0； 0|1=1； 1|0=1； 1|1=1；
总结：两边只要有一个为1结果就为1。
例如:3|5　即 00000011 | 0000 0101 = 00000111 因此，3|5的值得7。
用途：
将一个二进制数的某些位置为1，
使这个二进制数和一个数（二进制数要置为1的对应位为1）进行或运算；

 0110 1100
| 0000 0011 ----------------
 0110 1111

3.^ (异或)
0^0=0； 0^1=1； 1^0=1； 1^1=0；
总结：两边不同的时候才为1.
用途：
（1）使特定位翻转，找一个数，对应X要翻转的各位，该数的对应位为1，其余位为零，此数与X对应位异或即可。

例：X=10101110，使X低4位翻转，用X ^0000 1111 = 1010 0001即可得到。
（2）与0相异或，保留原值，X ^ 00000000 = 1010 1110。

下面重点说一下按位异或,异或其实就是不进位加法,如1+1=0，,0+0=0,1+0=1。
1、交换律

2、结合律（即(a^b)^c == a^(b^c)）

3、对于任何数x，都有x^x=0，x^0=x

4、自反性: a^b^b=a^0=a;

/* 1-1000放在含有1001个元素的数组中，只有唯一的一个元素值重复，其它均只出现 一次。每个数组元素只能访问一次，设计一个算法，将它找出来；不用辅助存储空 间，能否设计一个算法实现？ */
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <bitset>
#include <cmath>
#include <iostream>
#include <stdlib.h>
using namespace std;
int main()
{
    int a[10];
    int x=0;
    for(int i=0;i<10;i++)
    {
        cin>>a[i];
    }
    for(int i=0;i<10;i++)
    {
        x^=a[i];
    }
    int y=0;
    for(int i=1;i<=9;i++)
    {
        y^=i;
    }
    x^=y;
    cout<<x<<endl;
}

左移运算符（<<）
将一个运算对象的各二进制位全部左移若干位（左边的二进制位丢弃，右边补0）。

例：a = a<< 2将a的二进制位左移2位，右补0，

左移1位后a = a *2;

若左移时舍弃的高位不包含1，则每左移一位，相当于该数乘以2。

右移运算符（>>）
将一个数的各二进制位全部右移若干位，正数左补0，负数左补1，右边丢弃。

操作数每右移一位，相当于该数除以2。

例如：a = a>> 2 将a的二进制位右移2位，

左补0 or 补1得看被移数是正还是负。

不同长度的数据进行位运算

如果两个不同长度的数据进行位运算时，系统会将二者按右端对齐，然后进行位运算。

以“与”运算为例说明如下：我们知道在C语言中long型占4个字节，int型占2个字节，如果一个long型数据与一个int型数据进行“与”运算，右端对齐后，左边不足的位依下面三种情况补足，

（1）如果整型数据为正数，左边补16个0。

（2）如果整型数据为负数，左边补16个1。

（3）如果整形数据为无符号数，左边也补16个0。

如：long a=123;int b=1;计算a& b。

如：long a=123;int b=-1;计算a& b。

如：long a=123;unsigned intb=1;计算a & b。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <bitset>
#include <cmath>
#include <iostream>
#include <stdlib.h>
using namespace std;
int main()
{
    int a=0x3f3f3f3f;
    cout<<hex<<a<<endl;///十六进制
    cout<<oct<<a<<endl;///八进制
    cout<<dec<<a<<endl;///十进制
    cout<<bitset<32>(a)<<endl;///二进制


    int b=a&0;
    int x=110;
    int y=x&15;

    int t=2;
    t^=2;
    int tt=t^0;
    cout<<tt<<endl;
    cout<<t<<endl;

    int c=4;
    int d=-4;
    c<<=1;
    cout<<"c=4左移后<<"<<c<<endl;
    c=4;
    c>>=1;
    cout<<"c=4右移后>>"<<c<<endl;
    d<<=1;
    cout<<"d=-4左移后<<"<<d<<endl;
    d=-4;
    d>>=1;
    cout<<"d=-4右移后>>"<<d<<endl;


    ///不同类型进行位运算
    long long  A=123;
    cout<<bitset<64>(A)<<endl;
    int B=1;
    cout<<bitset<32>(B)<<endl;
    A=A&B;
    cout<<"A="<<A<<endl;
    B=-1;
    cout<<bitset<32>(B)<<endl;///负数在二进制中以补码形式存储
    A=123;
    A&=B;
    cout<<"A="<<A<<endl;
    A=123;
    unsigned int C=1;
    A&=C;
    cout<<"A="<<A<<endl;

    cout<<a<<" "<<b<<" "<<bitset<32>(x)<<" "<<bitset<32>(y)<<endl;
}