位移运算符
位移运算符有两种,左移运算符 << 和 右移运算符 >>
箭头指向哪,就是往哪移;
左移运算符 <<
将一个数的各二进制位全部左移若干位,右补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 0101
int b = 3; // 0000 0011
a ^= b; // 0000 0110
|=
两个二进制对应位为0时该位为0,否则为1 。
int a = 5; // 0000 0101
int b = 3; // 0000 0011
a |= b; // 0000 0111
&=
两个二进制对应位都为1时,结果为1,否则结果为都0。
int a = 5; // 0000 0101
int b = 3; // 0000 0011
a &= 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;
}
若有收获,就点个赞吧!