位运算的基础知识

位移运算符

位移运算符有两种，左移运算符 << 和 右移运算符 >>

箭头指向哪，就是往哪移；

左移运算符 <<

将一个数的各二进制位全部左移若干位，右补0；高位左移后溢出，舍弃；

int a = 3<<2;

是将数字3左移2位。即00000011----->00001100；

a的结果就是12；

右移运算符 >>

将一个数的各二进制位全部右移若干位， 高位的空位补符号位，即正数补0，负数补1；低位右移后溢出，舍弃；

int b = 11 >> 2;

是将数字11右移2位，即00001011------>00000010；

b的结果就是2；

二进制

对于二进制的左移或者右移，那么就有一个很巧妙的用法了；

对1进行左移可以用来表示2的几次方；

int c =1<<2; // 2的2次方；00000001------>00000100；
int d =1<<4; // 2的4次方；00000001------>00010000；

运算符 |=、&=、^=

^=位异或

a^=b等价于a = a^b，其中^是位异或运算，即将a与b的对应位进行异或运算，同为0或者同为1时，对应位结果为0；否则为1。

假设，a的值为二进制的1010，b的值为二进制的1100，那么a^b = 0110。

    int a = 5; // 0000 0101int b = 3; // 0000 0011a ^= b; // 0000 0110

|=

两个二进制对应位为0时该位为0，否则为1 。

   int a = 5; // 0000 0101int b = 3; // 0000 0011a |= b; // 0000 0111

&=

两个二进制对应位都为1时，结果为1，否则结果为都0。

    int a = 5; // 0000 0101int b = 3; // 0000 0011a &= b; // 0000 0001

秦九韶算法

将几个n进制的数转换成十进制

int get(string s,int b) //将b进制的数转化成十进制
{int res = 0;//秦九韶算法for(auto c: s)res = res * b +c-'0';return res;
}

以二进制为例

s = 10101;

b = 2;

位运算的两种常用操作

n的二进制表示中第k位是几（从个位算）

先把第k位移到最后一位 用右移 >>

看个位是几 n>>k & 1;

1的话是0000 0001

除了最后一位，前面全是0，所以可以看出来最后一位是什么

int main()
{int n=10;cout<<(n>>1&1);return 0;} 
//输出是1，因为10的二进制是1010，右移一位后变成101；
//&是  同为1才为1

位运算 —— 模板

求n的第k位数字: n >> k & 1
返回n的最后一位1：lowbit(n) = n & -n

lowbit 操作 ，树状数组的一种操作

lowbit(x) 返回x的最后一位1；

x=1010 lowbit(x) = 10;

x=101000 lowbit(x) = 1000;

int i = 3;
//3的二进制是11；
int t = i&-1;
//t = 1;
i -= t;
//i = 2;2的二进制是10；
t = i&-1;
//t = 2;
i -= t;

x& -x =x&(--x+1)

作用 ： 统计x里面1的个数

//用lowbit函数统计x里面1的个数
int lowbit(int x)
{int ans;while(x){x-=x&-x;s++;}return ans;
}

若有收获，就点个赞吧！