无苦邪

V1

2022/12/12阅读:22主题:橙心

小白学算法(5)之位运算

开启掘金成长之旅!这是我参与「掘金日新计划 · 12 月更文挑战」的第9天,点击查看活动详情[1]

位运算

1.十进制与二进制的转换

位运算是针对于2进制而言,所以进行运算时首先要将数字进行转换2进制,这里介绍8421法

十进制 二进制

1 0001

2 0010

4 0100

8 1000

16 10000

.....

这就是所谓8421法,这样可以很快进行十进制和二进制的转换

如5=4+1

0100+0001=0101

2.模板

(1)求n的第k位数字: n >> k & 1

那么我们这里就要先理解一下>>和<<运算符了

1)<<左移运算符 5<<2 左移两位 0101<<2-->0101 00=20 将一个运算对象的各二进制位全部左移若干位(左边的二进制丢弃,右边补0) 对于一个正数(无符号数)而言,左移1位就相当于*2,可以参考上面的8421法就可得知

2)>>右移运算符 5>>2 右移两位 0101>>2-->0001|(01)=1 正负数右移就不一样了 将一个运算对象的各二进制位全部右移若干位,正数左补0,负数左补1. 对于一个正数(无符号数)而言,左移1位就相当于/2,可以参考上面的8421法就可得知

3)& 按位与 这里要与&&进行区分,&&是逻辑运算符 所得到的结果真/假,只适用于编程语言中 因为不同语言的返回值不同,比如Java返回是true/false,C返回1/0 1&&0=假 1&&1=真,0&&0=假, 而&是按位运算符 使用范围较广,算法 即全1为1,其他全为0 1&1=1,1&0=0,0&0=0

解释模板: 理解了上面三种运算符,就可以很好解释该模板 n>>k:求第几位就左移几位,注意这里的第几位是从右向左算,并且0开始。使得所求位成为最后一位 &1:1转换为二进制即 00000000000000001,前面全0,只有最后一位为1,所以只会求得最后一位

(2).返回n的最后一位1:lowbit(n) = n & -n

&是二进制的运算

所以这里需要理解一个概念

-n的原码=n的原码取反+1(~n+1), ~就是取反的意思

5(0101)

~5(1010)

~5+1(1011)

所以5&(-5)=(0101)&(1011)=(0001) 得到的最后一位1为0001 ,第二个1是 0100=4

为什么这样可以得到最后一位1呢,我由图解释

我们可以得到最后一位1之后的所有位都为0,取反 后最后一位1变成了0,后面所有的0都变成了1,此时再+1 ,后面的1都会形成进位到最后一位1所取反的0

(鼠标画图太难了,以后用平板画🥲)

(3)实际应用

801. 二进制中1的个数 - AcWing题库

给定一个长度为 nn 的数列,请你求出数列中每个数的二进制表示中 1的个数。

通过上面模板我们可以求出最后一位1的数,我们可以去掉最后一位1的数,然后使得倒数第二位1的成为最后一位

#include<iostream>
using namespace std;
const int MAX=1e5+10;
int A[MAX];
int lowbit(int x)
{
    return x&(-x);  -x=~x+1 为x的补码
}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int res=0;
        cin>>A[i];
        //判断是否还有1
        while(lowbit(A[i]!=0))
        {
           //减去最后一位1的数,下一次判断就是倒数第二位的了
         A[i]-=lowbit(A[i]);res++;
        }
        cout<<res<<" ";
    }
    return 0;
}

位运算是针对于二进制而言,所以多于很多还不了解二进制运算的帅读者有点困难,但理解原理便变得通达了,毕竟二进制除了位数较多外,它的值只有1/0

感谢观看。😁

参考资料

[1]

https://juejin.cn/post/7167294154827890702: https://juejin.cn/post/7167294154827890702

分类:

后端

标签:

C++

作者介绍

无苦邪
V1