位运算

位移运算符

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

箭头指向哪,就是往哪移;

左移运算符 <<

将一个数的各二进制位全部左移若干位,右补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;
}

 

     
上一篇:python安装HTMLTestRunner


下一篇:比较两个日期时间大小